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 #include <gecode/minimodel.hh>
00039 #include <gecode/search.hh>
00040
00041 #include "test/test.hh"
00042
00043 namespace Test {
00044
00046 namespace Search {
00047
00048 using namespace Gecode;
00049 using namespace Gecode::Int;
00050
00052 enum HowToBranch {
00053 HTB_NONE,
00054 HTB_UNARY,
00055 HTB_BINARY,
00056 HTB_NARY
00057 };
00058
00060 enum HowToConstrain {
00061 HTC_NONE,
00062 HTC_LEX_LE,
00063 HTC_LEX_GR,
00064 HTC_BAL_LE,
00065 HTC_BAL_GR
00066 };
00067
00069 enum WhichModel {
00070 WM_FAIL_IMMEDIATE,
00071 WM_FAIL_SEARCH,
00072 WM_SOLUTIONS
00073 };
00074
00076 class TestSpace : public Space {
00077 public:
00079 TestSpace(void) {}
00081 TestSpace(bool share, TestSpace& s) : Space(share,s) {}
00083 virtual int solutions(void) const = 0;
00085 virtual bool best(void) const = 0;
00086 };
00087
00089 class FailImmediate : public TestSpace {
00090 public:
00092 IntVarArray x;
00094 FailImmediate(HowToBranch, HowToBranch, HowToBranch,
00095 HowToConstrain=HTC_NONE)
00096 : x(*this,1,0,0) {
00097 rel(*this, x[0], IRT_EQ, 1);
00098 }
00100 FailImmediate(bool share, FailImmediate& s) : TestSpace(share,s) {
00101 x.update(*this, share, s.x);
00102 }
00104 virtual Space* copy(bool share) {
00105 return new FailImmediate(share,*this);
00106 }
00108 virtual void constrain(const Space&) {
00109 }
00111 virtual int solutions(void) const {
00112 return 0;
00113 }
00115 virtual bool best(void) const {
00116 return false;
00117 }
00119 static std::string name(void) {
00120 return "Fail";
00121 }
00122 };
00123
00125 class HasSolutions : public TestSpace {
00126 public:
00128 IntVarArray x;
00130 HowToBranch htb1, htb2, htb3;
00132 HowToConstrain htc;
00134 void branch(const IntVarArgs& x, HowToBranch htb) {
00135 switch (htb) {
00136 case HTB_NONE:
00137 break;
00138 case HTB_UNARY:
00139 assign(*this, x, INT_ASSIGN_MIN);
00140 break;
00141 case HTB_BINARY:
00142 Gecode::branch(*this, x, INT_VAR_NONE, INT_VAL_MIN);
00143 break;
00144 case HTB_NARY:
00145 Gecode::branch(*this, x, INT_VAR_NONE, INT_VALUES_MIN);
00146 break;
00147 }
00148 }
00150 HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00151 HowToConstrain _htc=HTC_NONE)
00152 : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
00153 distinct(*this, x);
00154 rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
00155 rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
00156 IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
00157 IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
00158 IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
00159 }
00161 HasSolutions(bool share, HasSolutions& s)
00162 : TestSpace(share,s),
00163 htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
00164 x.update(*this, share, s.x);
00165 }
00167 virtual Space* copy(bool share) {
00168 return new HasSolutions(share,*this);
00169 }
00171 virtual void constrain(const Space& _s) {
00172 const HasSolutions& s = static_cast<const HasSolutions&>(_s);
00173 switch (htc) {
00174 case HTC_NONE:
00175 break;
00176 case HTC_LEX_LE:
00177 case HTC_LEX_GR:
00178 {
00179 IntVarArgs y(6);
00180 for (int i=0; i<6; i++)
00181 y[i].init(*this, s.x[i].val(), s.x[i].val());
00182 lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
00183 break;
00184 }
00185 case HTC_BAL_LE:
00186 case HTC_BAL_GR:
00187 {
00188 IntVarArgs y(6);
00189 for (int i=0; i<6; i++)
00190 y[i].init(*this, s.x[i].val(), s.x[i].val());
00191 IntVar xs(*this, -18, 18);
00192 IntVar ys(*this, -18, 18);
00193 post(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
00194 post(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
00195 rel(*this,
00196 abs(*this,xs),
00197 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
00198 abs(*this,ys));
00199 break;
00200 }
00201 }
00202 }
00204 virtual int solutions(void) const {
00205 if (htb1 == HTB_NONE) {
00206 assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
00207 return 1;
00208 }
00209 if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
00210 return 0;
00211 if (htb3 == HTB_UNARY)
00212 return 4;
00213 return 8;
00214 }
00216 virtual bool best(void) const {
00217 if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
00218 (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
00219 return true;
00220 switch (htc) {
00221 case HTC_NONE:
00222 return true;
00223 case HTC_LEX_LE:
00224 return ((x[0].val()==4) && (x[1].val()==5) &&
00225 (x[2].val()==2) && (x[3].val()==3) &&
00226 (x[4].val()==0) && (x[5].val()==1));
00227 case HTC_LEX_GR:
00228 return ((x[0].val()==5) && (x[1].val()==4) &&
00229 (x[2].val()==3) && (x[3].val()==2) &&
00230 (x[4].val()==1) && (x[5].val()==0));
00231 case HTC_BAL_LE:
00232 return ((x[0].val()==4) && (x[1].val()==5) &&
00233 (x[2].val()==2) && (x[3].val()==3) &&
00234 (x[4].val()==0) && (x[5].val()==1));
00235 case HTC_BAL_GR:
00236 return ((x[0].val()==4) && (x[1].val()==5) &&
00237 (x[2].val()==3) && (x[3].val()==2) &&
00238 (x[4].val()==0) && (x[5].val()==1));
00239 default: GECODE_NEVER;
00240 }
00241 return false;
00242 }
00244 static std::string name(void) {
00245 return "Sol";
00246 }
00247 };
00248
00250 class Test : public Base {
00251 public:
00253 HowToBranch htb1, htb2, htb3;
00255 HowToConstrain htc;
00257 static std::string str(unsigned int i) {
00258 std::stringstream s;
00259 s << i;
00260 return s.str();
00261 }
00263 static std::string str(HowToBranch htb) {
00264 switch (htb) {
00265 case HTB_NONE: return "None";
00266 case HTB_UNARY: return "Unary";
00267 case HTB_BINARY: return "Binary";
00268 case HTB_NARY: return "Nary";
00269 default: GECODE_NEVER;
00270 }
00271 GECODE_NEVER;
00272 return "";
00273 }
00275 static std::string str(HowToConstrain htc) {
00276 switch (htc) {
00277 case HTC_NONE: return "None";
00278 case HTC_LEX_LE: return "LexLe";
00279 case HTC_LEX_GR: return "LexGr";
00280 case HTC_BAL_LE: return "BalLe";
00281 case HTC_BAL_GR: return "BalGr";
00282 default: GECODE_NEVER;
00283 }
00284 GECODE_NEVER;
00285 return "";
00286 }
00288 Test(const std::string& s,
00289 HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00290 HowToConstrain _htc=HTC_NONE)
00291 : Base("Search::"+s),
00292 htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
00293 };
00294
00296 template<class Model>
00297 class DFS : public Test {
00298 private:
00300 unsigned int c_d;
00302 unsigned int a_d;
00304 unsigned int t;
00305 public:
00307 DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00308 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00309 : Test("DFS::"+Model::name()+"::"+
00310 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00311 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00312 htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
00314 virtual bool run(void) {
00315 Model* m = new Model(htb1,htb2,htb3);
00316 Gecode::Search::FailStop f(2);
00317 Gecode::Search::Options o;
00318 o.c_d = c_d;
00319 o.a_d = a_d;
00320 o.threads = t;
00321 o.stop = &f;
00322 Gecode::DFS<Model> dfs(m,o);
00323 int n = m->solutions();
00324 delete m;
00325 while (true) {
00326 Model* s = dfs.next();
00327 if (s != NULL) {
00328 n--; delete s;
00329 }
00330 if ((s == NULL) && !dfs.stopped())
00331 break;
00332 f.limit(f.limit()+2);
00333 }
00334 return n == 0;
00335 }
00336 };
00337
00339 template<class Model>
00340 class LDS : public Test {
00341 private:
00343 unsigned int t;
00344 public:
00346 LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00347 unsigned int t0)
00348 : Test("LDS::"+Model::name()+"::"+
00349 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
00350 htb1,htb2,htb3), t(t0) {}
00352 virtual bool run(void) {
00353 Model* m = new Model(htb1,htb2,htb3);
00354 Gecode::Search::FailStop f(2);
00355 Gecode::Search::Options o;
00356 o.threads = t;
00357 o.d = 50;
00358 o.stop = &f;
00359 Gecode::LDS<Model> lds(m,o);
00360 int n = m->solutions();
00361 delete m;
00362 while (true) {
00363 Model* s = lds.next();
00364 if (s != NULL) {
00365 n--; delete s;
00366 }
00367 if ((s == NULL) && !lds.stopped())
00368 break;
00369 f.limit(f.limit()+2);
00370 }
00371 return n == 0;
00372 }
00373 };
00374
00376 template<class Model, template<class> class Engine>
00377 class Best : public Test {
00378 private:
00380 unsigned int c_d;
00382 unsigned int a_d;
00384 unsigned int t;
00385 public:
00387 Best(const std::string& b, HowToConstrain htc,
00388 HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00389 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00390 : Test(b+"::"+Model::name()+"::"+str(htc)+"::"+
00391 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00392 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00393 htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
00395 virtual bool run(void) {
00396 Model* m = new Model(htb1,htb2,htb3,htc);
00397 Gecode::Search::FailStop f(2);
00398 Gecode::Search::Options o;
00399 o.c_d = c_d;
00400 o.a_d = a_d;
00401 o.threads = t;
00402 o.stop = &f;
00403 Engine<Model> best(m,o);
00404 delete m;
00405 Model* b = NULL;
00406 while (true) {
00407 Model* s = best.next();
00408 if (s != NULL) {
00409 delete b; b=s;
00410 }
00411 if ((s == NULL) && !best.stopped())
00412 break;
00413 f.limit(f.limit()+2);
00414 }
00415 bool ok = (b == NULL) || b->best();
00416 delete b;
00417 return ok;
00418 }
00419 };
00420
00422 class BranchTypes {
00423 private:
00425 static const HowToBranch htbs[3];
00427 int i;
00428 public:
00430 BranchTypes(void) : i(0) {}
00432 bool operator()(void) const {
00433 return i<3;
00434 }
00436 void operator++(void) {
00437 i++;
00438 }
00440 HowToBranch htb(void) const {
00441 return htbs[i];
00442 }
00443 };
00444
00445 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
00446
00448 class ConstrainTypes {
00449 private:
00451 static const HowToConstrain htcs[4];
00453 int i;
00454 public:
00456 ConstrainTypes(void) : i(0) {}
00458 bool operator()(void) const {
00459 return i<4;
00460 }
00462 void operator++(void) {
00463 i++;
00464 }
00466 HowToConstrain htc(void) const {
00467 return htcs[i];
00468 }
00469 };
00470
00471 const HowToConstrain ConstrainTypes::htcs[4] =
00472 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
00473
00474
00476 class Create {
00477 public:
00479 Create(void) {
00480
00481 for (unsigned int t = 1; t<=4; t++)
00482 for (unsigned int c_d = 1; c_d<10; c_d++)
00483 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00484 for (BranchTypes htb1; htb1(); ++htb1)
00485 for (BranchTypes htb2; htb2(); ++htb2)
00486 for (BranchTypes htb3; htb3(); ++htb3)
00487 (void) new DFS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb(),
00488 c_d, a_d, t);
00489 new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00490 c_d, a_d, t);
00491 new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
00492 c_d, a_d, t);
00493 }
00494
00495
00496 for (unsigned int t = 1; t<=4; t++) {
00497 for (BranchTypes htb1; htb1(); ++htb1)
00498 for (BranchTypes htb2; htb2(); ++htb2)
00499 for (BranchTypes htb3; htb3(); ++htb3)
00500 (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
00501 ,t);
00502 new LDS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE, t);
00503 new LDS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE, t);
00504 }
00505
00506
00507 for (unsigned int t = 1; t<=4; t++)
00508 for (unsigned int c_d = 1; c_d<10; c_d++)
00509 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00510 for (ConstrainTypes htc; htc(); ++htc)
00511 for (BranchTypes htb1; htb1(); ++htb1)
00512 for (BranchTypes htb2; htb2(); ++htb2)
00513 for (BranchTypes htb3; htb3(); ++htb3) {
00514 (void) new Best<HasSolutions,BAB>
00515 ("BAB",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00516 c_d,a_d,t);
00517 (void) new Best<HasSolutions,Restart>
00518 ("Restart",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00519 c_d,a_d,t);
00520 }
00521 (void) new Best<FailImmediate,BAB>
00522 ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00523 (void) new Best<HasSolutions,BAB>
00524 ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00525 }
00526
00527 }
00528 };
00529
00530 Create c;
00531 }
00532
00533 }
00534
00535