Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
bibd.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Bugfixes provided by:
10  * Olof Sivertsson <olsi0767@student.uu.se>
11  *
12  * This file is part of Gecode, the generic constraint
13  * development environment:
14  * http://www.gecode.org
15  *
16  * Permission is hereby granted, free of charge, to any person obtaining
17  * a copy of this software and associated documentation files (the
18  * "Software"), to deal in the Software without restriction, including
19  * without limitation the rights to use, copy, modify, merge, publish,
20  * distribute, sublicense, and/or sell copies of the Software, and to
21  * permit persons to whom the Software is furnished to do so, subject to
22  * the following conditions:
23  *
24  * The above copyright notice and this permission notice shall be
25  * included in all copies or substantial portions of the Software.
26  *
27  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34  *
35  */
36 
37 #include <gecode/driver.hh>
38 #include <gecode/int.hh>
39 
40 using namespace Gecode;
41 
46 class BIBDOptions : public Options {
47 public:
48  int v, k, lambda;
49  int b, r;
50  void derive(void) {
52  b = (v*(v-1)*lambda)/(k*(k-1));
53  r = (lambda*(v-1)) / (k-1);
54  }
56  BIBDOptions(const char* s,
57  int v0, int k0, int lambda0)
58  : Options(s), v(v0), k(k0), lambda(lambda0) {
59  derive();
60  }
62  void parse(int& argc, char* argv[]) {
63  Options::parse(argc,argv);
64  if (argc < 4)
65  return;
66  v = atoi(argv[1]);
67  k = atoi(argv[2]);
68  lambda = atoi(argv[3]);
69  derive();
70  }
72  virtual void help(void) {
73  Options::help();
74  std::cerr << "\t(unsigned int) default: " << v << std::endl
75  << "\t\tparameter v" << std::endl
76  << "\t(unsigned int) default: " << k << std::endl
77  << "\t\tparameter k" << std::endl
78  << "\t(unsigned int) default: " << lambda << std::endl
79  << "\t\tparameter lambda" << std::endl;
80  }
81 };
82 
83 
92 class BIBD : public Script {
93 protected:
95  const BIBDOptions& opt;
98 public:
100  enum {
103  SYMMETRY_LDSB
104  };
105 
107  BIBD(const BIBDOptions& o)
108  : Script(o), opt(o), _p(*this,opt.v*opt.b,0,1) {
109  Matrix<BoolVarArray> p(_p,opt.b,opt.v);
110 
111  // r ones per row
112  for (int i=0; i<opt.v; i++)
113  linear(*this, p.row(i), IRT_EQ, opt.r);
114 
115  // k ones per column
116  for (int j=0; j<opt.b; j++)
117  linear(*this, p.col(j), IRT_EQ, opt.k);
118 
119  // Exactly lambda ones in scalar product between two different rows
120  for (int i1=0; i1<opt.v; i1++)
121  for (int i2=i1+1; i2<opt.v; i2++) {
122  BoolVarArgs row(opt.b);
123  for (int j=0; j<opt.b; j++)
124  row[j] = expr(*this, p(j,i1) && p(j,i2));
125  linear(*this, row, IRT_EQ, opt.lambda);
126  }
127 
128  if (opt.symmetry() == SYMMETRY_LDSB) {
129  Symmetries s;
130  s << rows_interchange(p);
131  s << columns_interchange(p);
132  branch(*this, _p, BOOL_VAR_NONE(), BOOL_VAL_MIN(), s);
133  } else {
134  if (opt.symmetry() == SYMMETRY_LEX) {
135  for (int i=1; i<opt.v; i++)
136  rel(*this, p.row(i-1), IRT_GQ, p.row(i));
137  for (int j=1; j<opt.b; j++)
138  rel(*this, p.col(j-1), IRT_GQ, p.col(j));
139  }
140  branch(*this, _p, BOOL_VAR_NONE(), BOOL_VAL_MIN());
141  }
142 
143  }
144 
146  virtual void
147  print(std::ostream& os) const {
148  os << "\tBIBD("
149  << opt.v << "," << opt.k << ","
150  << opt.lambda << ")" << std::endl;
151  Matrix<BoolVarArray> p(_p,opt.b,opt.v);
152  for (int i = 0; i<opt.v; i++) {
153  os << "\t\t";
154  for (int j = 0; j<opt.b; j++)
155  os << p(j,i) << " ";
156  os << std::endl;
157  }
158  os << std::endl;
159  }
160 
162  BIBD(BIBD& s)
163  : Script(s), opt(s.opt) {
164  _p.update(*this, s._p);
165  }
166 
168  virtual Space*
169  copy(void) {
170  return new BIBD(*this);
171  }
172 
173 };
174 
178 int
179 main(int argc, char* argv[]) {
180  BIBDOptions opt("BIBD",7,3,60);
181 
183  opt.symmetry(BIBD::SYMMETRY_NONE,"none");
184  opt.symmetry(BIBD::SYMMETRY_LEX,"lex");
185  opt.symmetry(BIBD::SYMMETRY_LDSB,"ldsb");
186 
187  opt.parse(argc,argv);
188 
189  /*
190  * Other interesting instances:
191  * BIBD(7,3,1), BIBD(6,3,2), BIBD(7,3,20), ...
192  */
193 
194  Script::run<BIBD,DFS,BIBDOptions>(opt);
195  return 0;
196 }
197 
198 // STATISTICS: example-any
199 
int r
Derived parameters Derive additional parameters.
Definition: bibd.cpp:49
Options for BIBD problems
Definition: bibd.cpp:46
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
LDSB on rows/columns.
Definition: bibd.cpp:103
int v
Definition: bibd.cpp:48
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
virtual void help(void)
Print help message.
Definition: bibd.cpp:72
BIBD(const BIBDOptions &o)
Actual model.
Definition: bibd.cpp:107
Collection of symmetries.
Definition: int.hh:5162
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
SymmetryHandle columns_interchange(const Matrix< A > &m)
Interchangeable columns symmetry specification.
Definition: ldsb.hpp:51
Computation spaces.
Definition: core.hpp:1701
Greater or equal ( )
Definition: int.hh:930
Parametric base-class for scripts.
Definition: driver.hh:729
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:130
int lambda
Parameters to be given on command line.
Definition: bibd.cpp:48
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
int b
Definition: bibd.cpp:49
Lex-constraints on rows/columns.
Definition: bibd.cpp:102
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
const BIBDOptions & opt
Options providing access to parameters.
Definition: bibd.cpp:95
BoolVarArray _p
Matrix of Boolean variables.
Definition: bibd.cpp:97
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: bibd.cpp:62
Example: Balanced incomplete block design (BIBD)
Definition: bibd.cpp:92
Passing Boolean variables.
Definition: int.hh:712
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:627
Boolean variable array.
Definition: int.hh:808
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:540
const int v[7]
Definition: distinct.cpp:259
int main(int argc, char *argv[])
Main-function.
Definition: bibd.cpp:179
No symmetry breaking.
Definition: bibd.cpp:101
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
void symmetry(int v)
Set default symmetry value.
Definition: options.hpp:190
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
BIBD(BIBD &s)
Constructor for cloning s.
Definition: bibd.cpp:162
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition: ldsb.hpp:40
virtual void print(std::ostream &os) const
Print solution.
Definition: bibd.cpp:147
Matrix-interface for arrays.
Definition: minimodel.hh:2048
Gecode toplevel namespace
int k
Definition: bibd.cpp:48
BIBDOptions(const char *s, int v0, int k0, int lambda0)
Initialize options for example with name s.
Definition: bibd.cpp:56
Options for scripts
Definition: driver.hh:366
virtual Space * copy(void)
Copy during cloning.
Definition: bibd.cpp:169
virtual void help(void)
Print help text.
Definition: options.cpp:486