bibd.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2004
*
* Bugfixes provided by:
* Olof Sivertsson <olsi0767@student.uu.se>
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
using namespace Gecode;
class BIBDOptions : public Options {
public:
int v, k, lambda;
int b, r;
void derive(void) {
b = (v*(v-1)*lambda)/(k*(k-1));
r = (lambda*(v-1)) / (k-1);
}
BIBDOptions(const char* s,
int v0, int k0, int lambda0)
: Options(s), v(v0), k(k0), lambda(lambda0) {
derive();
}
void parse(int& argc, char* argv[]) {
Options::parse(argc,argv);
if (argc < 4)
return;
v = atoi(argv[1]);
k = atoi(argv[2]);
lambda = atoi(argv[3]);
derive();
}
virtual void help(void) {
Options::help();
std::cerr << "\t(unsigned int) default: " << v << std::endl
<< "\t\tparameter v" << std::endl
<< "\t(unsigned int) default: " << k << std::endl
<< "\t\tparameter k" << std::endl
<< "\t(unsigned int) default: " << lambda << std::endl
<< "\t\tparameter lambda" << std::endl;
}
};
class BIBD : public Script {
protected:
const BIBDOptions& opt;
BoolVarArray _p;
public:
enum {
SYMMETRY_NONE,
SYMMETRY_LEX,
SYMMETRY_LDSB
};
BIBD(const BIBDOptions& o)
: Script(o), opt(o), _p(*this,opt.v*opt.b,0,1) {
Matrix<BoolVarArray> p(_p,opt.b,opt.v);
// r ones per row
for (int i=0; i<opt.v; i++)
linear(*this, p.row(i), IRT_EQ, opt.r);
// k ones per column
for (int j=0; j<opt.b; j++)
linear(*this, p.col(j), IRT_EQ, opt.k);
// Exactly lambda ones in scalar product between two different rows
for (int i1=0; i1<opt.v; i1++)
for (int i2=i1+1; i2<opt.v; i2++) {
BoolVarArgs row(opt.b);
for (int j=0; j<opt.b; j++)
row[j] = expr(*this, p(j,i1) && p(j,i2));
linear(*this, row, IRT_EQ, opt.lambda);
}
if (opt.symmetry() == SYMMETRY_LDSB) {
Symmetries s;
s << rows_interchange(p);
s << columns_interchange(p);
branch(*this, _p, BOOL_VAR_NONE(), BOOL_VAL_MIN(), s);
} else {
if (opt.symmetry() == SYMMETRY_LEX) {
for (int i=1; i<opt.v; i++)
rel(*this, p.row(i-1), IRT_GQ, p.row(i));
for (int j=1; j<opt.b; j++)
rel(*this, p.col(j-1), IRT_GQ, p.col(j));
}
branch(*this, _p, BOOL_VAR_NONE(), BOOL_VAL_MIN());
}
}
virtual void
print(std::ostream& os) const {
os << "\tBIBD("
<< opt.v << "," << opt.k << ","
<< opt.lambda << ")" << std::endl;
Matrix<BoolVarArray> p(_p,opt.b,opt.v);
for (int i = 0; i<opt.v; i++) {
os << "\t\t";
for (int j = 0; j<opt.b; j++)
os << p(j,i) << " ";
os << std::endl;
}
os << std::endl;
}
BIBD(BIBD& s)
: Script(s), opt(s.opt) {
_p.update(*this, s._p);
}
virtual Space*
copy(void) {
return new BIBD(*this);
}
};
int
main(int argc, char* argv[]) {
BIBDOptions opt("BIBD",7,3,60);
opt.symmetry(BIBD::SYMMETRY_LEX);
opt.symmetry(BIBD::SYMMETRY_NONE,"none");
opt.symmetry(BIBD::SYMMETRY_LEX,"lex");
opt.symmetry(BIBD::SYMMETRY_LDSB,"ldsb");
opt.parse(argc,argv);
/*
* Other interesting instances:
* BIBD(7,3,1), BIBD(6,3,2), BIBD(7,3,20), ...
*/
Script::run<BIBD,DFS,BIBDOptions>(opt);
return 0;
}
// STATISTICS: example-any
BIBDOptions
Options for BIBD problems
Definition bibd.cpp:46
BIBDOptions::b
int b
Definition bibd.cpp:49
BIBDOptions::v
int v
Definition bibd.cpp:48
BIBDOptions::lambda
int lambda
Parameters to be given on command line.
Definition bibd.cpp:48
BIBDOptions::help
virtual void help(void)
Print help message.
Definition bibd.cpp:72
BIBDOptions::r
int r
Derived parameters Derive additional parameters.
Definition bibd.cpp:49
BIBDOptions::parse
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc).
Definition bibd.cpp:62
BIBDOptions::BIBDOptions
BIBDOptions(const char *s, int v0, int k0, int lambda0)
Initialize options for example with name s.
Definition bibd.cpp:56
BIBDOptions::k
int k
Definition bibd.cpp:48
BIBDOptions::derive
void derive(void)
Definition bibd.cpp:51
BIBD::main
int main(int argc, char *argv[])
Main-function.
Definition bibd.cpp:179
BIBD::opt
const BIBDOptions & opt
Options providing access to parameters.
Definition bibd.cpp:95
BIBD::BIBD
BIBD(const BIBDOptions &o)
Actual model.
Definition bibd.cpp:107
BIBD::_p
BoolVarArray _p
Matrix of Boolean variables.
Definition bibd.cpp:97
BIBD::copy
virtual Space * copy(void)
Copy during cloning.
Definition bibd.cpp:169
BIBD::BIBD
BIBD(BIBD &s)
Constructor for cloning s.
Definition bibd.cpp:162
BIBD::SYMMETRY_LEX
@ SYMMETRY_LEX
Lex-constraints on rows/columns.
Definition bibd.cpp:102
BIBD::SYMMETRY_LDSB
@ SYMMETRY_LDSB
LDSB on rows/columns.
Definition bibd.cpp:103
BIBD::SYMMETRY_NONE
@ SYMMETRY_NONE
No symmetry breaking.
Definition bibd.cpp:101
BIBD::print
virtual void print(std::ostream &os) const
Print solution.
Definition bibd.cpp:147
Gecode::BaseOptions::help
virtual void help(void)
Print help text.
Definition options.cpp:494
Gecode::BaseOptions::parse
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc).
Definition options.cpp:548
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:808
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::Matrix::col
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Gecode::Matrix::row
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Gecode::Options::Options
Options(const char *s)
Initialize options for script with name s.
Definition options.cpp:576
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Symmetries
Collection of symmetries.
Definition int.hh:5292
driver.hh
int.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
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
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:930
Gecode
Gecode toplevel namespace
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::BOOL_VAL_MIN
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition val.hpp:130
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Gecode::rows_interchange
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition ldsb.hpp:40
Gecode::columns_interchange
SymmetryHandle columns_interchange(const Matrix< A > &m)
Interchangeable columns symmetry specification.
Definition ldsb.hpp:51