Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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;
51  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 
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 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:629
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Options for BIBD problems
Definition: bibd.cpp:46
int b
Definition: bibd.cpp:49
virtual void help(void)
Print help message.
Definition: bibd.cpp:72
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: bibd.cpp:62
BIBDOptions(const char *s, int v0, int k0, int lambda0)
Initialize options for example with name s.
Definition: bibd.cpp:56
int k
Definition: bibd.cpp:48
void derive(void)
Definition: bibd.cpp:51
Example: Balanced incomplete block design (BIBD)
Definition: bibd.cpp:92
int main(int argc, char *argv[])
Main-function.
Definition: bibd.cpp:179
const BIBDOptions & opt
Options providing access to parameters.
Definition: bibd.cpp:95
BIBD(const BIBDOptions &o)
Actual model.
Definition: bibd.cpp:107
BoolVarArray _p
Matrix of Boolean variables.
Definition: bibd.cpp:97
BIBD(BIBD &s)
Constructor for cloning s.
Definition: bibd.cpp:162
@ SYMMETRY_LEX
Lex-constraints on rows/columns.
Definition: bibd.cpp:102
@ SYMMETRY_LDSB
LDSB on rows/columns.
Definition: bibd.cpp:103
@ SYMMETRY_NONE
No symmetry breaking.
Definition: bibd.cpp:101
virtual Space * copy(void)
Copy during cloning.
Definition: bibd.cpp:169
virtual void print(std::ostream &os) const
Print solution.
Definition: bibd.cpp:147
virtual void help(void)
Print help text.
Definition: options.cpp:494
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
Passing Boolean variables.
Definition: int.hh:712
Boolean variable array.
Definition: int.hh:808
Parametric base-class for scripts.
Definition: driver.hh:729
Matrix-interface for arrays.
Definition: minimodel.hh:2161
Options for scripts
Definition: driver.hh:366
void symmetry(int v)
Set default symmetry value.
Definition: options.hpp:190
Computation spaces.
Definition: core.hpp:1742
Collection of symmetries.
Definition: int.hh:5292
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
@ IRT_EQ
Equality ( )
Definition: int.hh:926
@ IRT_GQ
Greater or equal ( )
Definition: int.hh:930
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:130
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition: ldsb.hpp:40
SymmetryHandle columns_interchange(const Matrix< A > &m)
Interchangeable columns symmetry specification.
Definition: ldsb.hpp:51
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
Options opt
The options.
Definition: test.cpp:97