Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
40using namespace Gecode;
41
46class BIBDOptions : public Options {
47public:
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 }
55
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
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
72 virtual void help(void) {
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
92class BIBD : public Script {
93protected:
98public:
100 enum {
104 };
105
108 : Script(o), opt(o), _p(*this,opt.v*opt.b,0,1) {
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;
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
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
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
195 return 0;
196}
197
198// STATISTICS: example-any
199
Options for BIBD problems
Definition bibd.cpp:46
int lambda
Parameters to be given on command line.
Definition bibd.cpp:48
virtual void help(void)
Print help message.
Definition bibd.cpp:72
int r
Derived parameters Derive additional parameters.
Definition bibd.cpp:49
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
void derive(void)
Definition bibd.cpp:51
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
virtual Space * copy(void)
Copy during cloning.
Definition bibd.cpp:169
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 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:721
Boolean variable array.
Definition int.hh:820
static void run(const Options &opt, Script *s=NULL)
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Options(const char *s)
Initialize options for script with name s.
Definition options.cpp:576
Computation spaces.
Definition core.hpp:1744
Collection of symmetries.
Definition int.hh:5307
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
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, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IRT_GQ
Greater or equal ( )
Definition int.hh:945
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
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