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 <gecode/driver.hh>
00042 #include <gecode/int.hh>
00043
00044 using namespace Gecode;
00045
00050 class BIBDOptions : public Options {
00051 public:
00052 int v, k, lambda;
00053 int b, r;
00054
00055 void derive(void) {
00056 b = (v*(v-1)*lambda)/(k*(k-1));
00057 r = (lambda*(v-1)) / (k-1);
00058 }
00060 BIBDOptions(const char* s,
00061 int v0, int k0, int lambda0)
00062 : Options(s), v(v0), k(k0), lambda(lambda0) {
00063 derive();
00064 }
00066 void parse(int& argc, char* argv[]) {
00067 Options::parse(argc,argv);
00068 if (argc < 4)
00069 return;
00070 v = atoi(argv[1]);
00071 k = atoi(argv[2]);
00072 lambda = atoi(argv[3]);
00073 derive();
00074 }
00076 virtual void help(void) {
00077 Options::help();
00078 std::cerr << "\t(unsigned int) default: " << v << std::endl
00079 << "\t\tparameter v" << std::endl
00080 << "\t(unsigned int) default: " << k << std::endl
00081 << "\t\tparameter k" << std::endl
00082 << "\t(unsigned int) default: " << lambda << std::endl
00083 << "\t\tparameter lambda" << std::endl;
00084 }
00085 };
00086
00087
00096 class BIBD : public Script {
00097 protected:
00099 const BIBDOptions& opt;
00101 BoolVarArray _p;
00102 public:
00104 BoolVar& p(int i, int j) {
00105
00106 return _p[i*opt.b+j];
00107 }
00109 const BoolVar& p(int i, int j) const {
00110
00111 return _p[i*opt.b+j];
00112 }
00114 BIBD(const BIBDOptions& o)
00115 : opt(o), _p(*this,opt.v*opt.b,0,1) {
00116
00117 for (int i=opt.v; i--; ) {
00118 BoolVarArgs row(opt.b);
00119 for (int j=opt.b; j--; )
00120 row[j] = p(i,j);
00121 linear(*this, row, IRT_EQ, opt.r);
00122 }
00123
00124 for (int j=opt.b; j--; ) {
00125 BoolVarArgs col(opt.v);
00126 for (int i=opt.v; i--; )
00127 col[i] = p(i,j);
00128 linear(*this, col, IRT_EQ, opt.k);
00129 }
00130
00131 for (int i1=0; i1<opt.v; i1++)
00132 for (int i2=i1+1; i2<opt.v; i2++) {
00133 BoolVarArgs row(opt.b);
00134 for (int j=opt.b; j--; ) {
00135 BoolVar b(*this,0,1);
00136 rel(*this,p(i1,j),BOT_AND,p(i2,j),b);
00137 row[j] = b;
00138 }
00139 linear(*this, row, IRT_EQ, opt.lambda);
00140 }
00141
00142 for (int i=1;i<opt.v;i++) {
00143 BoolVarArgs row1(opt.b);
00144 BoolVarArgs row2(opt.b);
00145 for (int j=opt.b; j--; ) {
00146 row1[j] = p(i-1,j);
00147 row2[j] = p(i,j);
00148 }
00149 rel(*this, row1, IRT_GQ, row2);
00150 }
00151 for (int j=1;j<opt.b;j++) {
00152 BoolVarArgs col1(opt.v);
00153 BoolVarArgs col2(opt.v);
00154 for (int i=opt.v; i--; ) {
00155 col1[i] = p(i,j-1);
00156 col2[i] = p(i,j);
00157 }
00158 rel(*this, col1, IRT_GQ, col2);
00159 }
00160
00161 branch(*this, _p, INT_VAR_NONE, INT_VAL_MIN);
00162 }
00163
00165 virtual void
00166 print(std::ostream& os) const {
00167 os << "\tBIBD("
00168 << opt.v << "," << opt.k << ","
00169 << opt.lambda << ")" << std::endl;
00170 for (int i = 0; i < opt.v; i++) {
00171 os << "\t\t";
00172 for (int j = 0; j< opt.b; j++)
00173 os << p(i,j) << " ";
00174 os << std::endl;
00175 }
00176 os << std::endl;
00177 }
00178
00180 BIBD(bool share, BIBD& s)
00181 : Script(share,s), opt(s.opt) {
00182 _p.update(*this,share,s._p);
00183 }
00184
00186 virtual Space*
00187 copy(bool share) {
00188 return new BIBD(share,*this);
00189 }
00190
00191 };
00192
00196 int
00197 main(int argc, char* argv[]) {
00198 BIBDOptions opt("BIBD",7,3,60);
00199 opt.parse(argc,argv);
00200
00201
00202
00203
00204
00205
00206 Script::run<BIBD,DFS,BIBDOptions>(opt);
00207 return 0;
00208 }
00209
00210
00211