00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #include "examples/support.hh"
00042
00047 class BIBDOptions : public Options {
00048 public:
00049 int v, k, lambda;
00050 int b, r;
00051
00052 void derive(void) {
00053 b = (v*(v-1)*lambda)/(k*(k-1));
00054 r = (lambda*(v-1)) / (k-1);
00055 }
00057 BIBDOptions(const char* s,
00058 int v0, int k0, int lambda0)
00059 : Options(s), v(v0), k(k0), lambda(lambda0) {
00060 derive();
00061 }
00063 void parse(int& argc, char* argv[]) {
00064 Options::parse(argc,argv);
00065 if (argc < 4)
00066 return;
00067 v = atoi(argv[1]);
00068 k = atoi(argv[2]);
00069 lambda = atoi(argv[3]);
00070 derive();
00071 }
00073 virtual void help(void) {
00074 Options::help();
00075 std::cerr << "\t(unsigned int) default: " << v << std::endl
00076 << "\t\tparameter v" << std::endl
00077 << "\t(unsigned int) default: " << k << std::endl
00078 << "\t\tparameter k" << std::endl
00079 << "\t(unsigned int) default: " << lambda << std::endl
00080 << "\t\tparameter lambda" << std::endl;
00081 }
00082 };
00083
00084
00093 class BIBD : public Example {
00094 protected:
00096 const BIBDOptions& opt;
00098 BoolVarArray _p;
00099 public:
00101 BoolVar& p(int i, int j) {
00102
00103 return _p[i*opt.b+j];
00104 }
00106 BIBD(const BIBDOptions& o)
00107 : opt(o), _p(this,opt.v*opt.b,0,1) {
00108
00109 for (int i=opt.v; i--; ) {
00110 BoolVarArgs row(opt.b);
00111 for (int j=opt.b; j--; )
00112 row[j] = p(i,j);
00113 linear(this, row, IRT_EQ, opt.r, ICL_DEF, opt.pk());
00114 }
00115
00116 for (int j=opt.b; j--; ) {
00117 BoolVarArgs col(opt.v);
00118 for (int i=opt.v; i--; )
00119 col[i] = p(i,j);
00120 linear(this, col, IRT_EQ, opt.k, ICL_DEF, opt.pk());
00121 }
00122
00123 for (int i1=0; i1<opt.v; i1++)
00124 for (int i2=i1+1; i2<opt.v; i2++) {
00125 BoolVarArgs row(opt.b);
00126 for (int j=opt.b; j--; ) {
00127 BoolVar b(this,0,1);
00128 rel(this,p(i1,j),BOT_AND,p(i2,j),b);
00129 row[j] = b;
00130 }
00131 linear(this, row, IRT_EQ, opt.lambda, ICL_DEF, opt.pk());
00132 }
00133
00134 for (int i=1;i<opt.v;i++) {
00135 BoolVarArgs row1(opt.b);
00136 BoolVarArgs row2(opt.b);
00137 for (int j=opt.b; j--; ) {
00138 row1[j] = p(i-1,j);
00139 row2[j] = p(i,j);
00140 }
00141 rel(this, row1, IRT_GQ, row2);
00142 }
00143 for (int j=1;j<opt.b;j++) {
00144 BoolVarArgs col1(opt.v);
00145 BoolVarArgs col2(opt.v);
00146 for (int i=opt.v; i--; ) {
00147 col1[i] = p(i,j-1);
00148 col2[i] = p(i,j);
00149 }
00150 rel(this, col1, IRT_GQ, col2);
00151 }
00152
00153 branch(this, _p, INT_VAR_NONE, INT_VAL_MIN);
00154 }
00155
00157 virtual void
00158 print(std::ostream& os) {
00159 os << "\tBIBD("
00160 << opt.v << "," << opt.k << ","
00161 << opt.lambda << ")" << std::endl;
00162 for (int i = 0; i < opt.v; i++) {
00163 os << "\t\t";
00164 for (int j = 0; j< opt.b; j++)
00165 os << p(i,j) << " ";
00166 os << std::endl;
00167 }
00168 os << std::endl;
00169 }
00170
00172 BIBD(bool share, BIBD& s)
00173 : Example(share,s), opt(s.opt) {
00174 _p.update(this,share,s._p);
00175 }
00176
00178 virtual Space*
00179 copy(bool share) {
00180 return new BIBD(share,*this);
00181 }
00182
00183 };
00184
00188 int
00189 main(int argc, char* argv[]) {
00190 BIBDOptions opt("BIBD",7,3,60);
00191 opt.parse(argc,argv);
00192
00193
00194
00195
00196
00197
00198 Example::run<BIBD,DFS,BIBDOptions>(opt);
00199 return 0;
00200 }
00201
00202
00203