this repo has no description
dekker.one
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
40using namespace Gecode;
41
42/**
43 * \brief %Options for %BIBD problems
44 *
45 */
46class BIBDOptions : public Options {
47public:
48 int v, k, lambda; ///< Parameters to be given on command line
49 int b, r; ///< Derived parameters
50 /// Derive additional parameters
51 void derive(void) {
52 b = (v*(v-1)*lambda)/(k*(k-1));
53 r = (lambda*(v-1)) / (k-1);
54 }
55 /// Initialize options for example with name \a s
56 BIBDOptions(const char* s,
57 int v0, int k0, int lambda0)
58 : Options(s), v(v0), k(k0), lambda(lambda0) {
59 derive();
60 }
61 /// Parse options from arguments \a argv (number is \a argc)
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 }
71 /// Print help message
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
84/**
85 * \brief %Example: Balanced incomplete block design (%BIBD)
86 *
87 * See problem 28 at http://www.csplib.org/.
88 *
89 * \ingroup Example
90 *
91 */
92class BIBD : public Script {
93protected:
94 /// Options providing access to parameters
95 const BIBDOptions& opt;
96 /// Matrix of Boolean variables
97 BoolVarArray _p;
98public:
99 /// Symmetry breaking variants
100 enum {
101 SYMMETRY_NONE, ///< No symmetry breaking
102 SYMMETRY_LEX, ///< Lex-constraints on rows/columns
103 SYMMETRY_LDSB ///< LDSB on rows/columns
104 };
105
106 /// Actual model
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
145 /// Print solution
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
161 /// Constructor for cloning \a s
162 BIBD(BIBD& s)
163 : Script(s), opt(s.opt) {
164 _p.update(*this, s._p);
165 }
166
167 /// Copy during cloning
168 virtual Space*
169 copy(void) {
170 return new BIBD(*this);
171 }
172
173};
174
175/** \brief Main-function
176 * \relates BIBD
177 */
178int
179main(int argc, char* argv[]) {
180 BIBDOptions opt("BIBD",7,3,60);
181
182 opt.symmetry(BIBD::SYMMETRY_LEX);
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