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 SolveImmediate : public TestSpace {
00126 public:
00128 IntVarArray x;
00130 SolveImmediate(HowToBranch, HowToBranch, HowToBranch,
00131 HowToConstrain=HTC_NONE)
00132 : x(*this,1,0,0) {}
00134 SolveImmediate(bool share, SolveImmediate& s) : TestSpace(share,s) {
00135 x.update(*this, share, s.x);
00136 }
00138 virtual Space* copy(bool share) {
00139 return new SolveImmediate(share,*this);
00140 }
00142 virtual void constrain(const Space&) {
00143 fail();
00144 }
00146 virtual int solutions(void) const {
00147 return 1;
00148 }
00150 virtual bool best(void) const {
00151 return true;
00152 }
00154 static std::string name(void) {
00155 return "Solve";
00156 }
00157 };
00158
00160 class HasSolutions : public TestSpace {
00161 public:
00163 IntVarArray x;
00165 HowToBranch htb1, htb2, htb3;
00167 HowToConstrain htc;
00169 void branch(const IntVarArgs& x, HowToBranch htb) {
00170 switch (htb) {
00171 case HTB_NONE:
00172 break;
00173 case HTB_UNARY:
00174 assign(*this, x, INT_ASSIGN_MIN());
00175 break;
00176 case HTB_BINARY:
00177 Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
00178 break;
00179 case HTB_NARY:
00180 Gecode::branch(*this, x, INT_VAR_NONE(), INT_VALUES_MIN());
00181 break;
00182 }
00183 }
00185 HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00186 HowToConstrain _htc=HTC_NONE)
00187 : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
00188 distinct(*this, x);
00189 rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
00190 rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
00191 IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
00192 IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
00193 IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
00194 }
00196 HasSolutions(bool share, HasSolutions& s)
00197 : TestSpace(share,s),
00198 htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
00199 x.update(*this, share, s.x);
00200 }
00202 virtual Space* copy(bool share) {
00203 return new HasSolutions(share,*this);
00204 }
00206 virtual void constrain(const Space& _s) {
00207 const HasSolutions& s = static_cast<const HasSolutions&>(_s);
00208 switch (htc) {
00209 case HTC_NONE:
00210 break;
00211 case HTC_LEX_LE:
00212 case HTC_LEX_GR:
00213 {
00214 IntVarArgs y(6);
00215 for (int i=0; i<6; i++)
00216 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
00217 lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
00218 break;
00219 }
00220 case HTC_BAL_LE:
00221 case HTC_BAL_GR:
00222 {
00223 IntVarArgs y(6);
00224 for (int i=0; i<6; i++)
00225 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
00226 IntVar xs(*this, -18, 18);
00227 IntVar ys(*this, -18, 18);
00228 rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
00229 rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
00230 rel(*this,
00231 expr(*this,abs(xs)),
00232 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
00233 expr(*this,abs(ys)));
00234 break;
00235 }
00236 }
00237 }
00239 virtual int solutions(void) const {
00240 if (htb1 == HTB_NONE) {
00241 assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
00242 return 1;
00243 }
00244 if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
00245 return 0;
00246 if (htb3 == HTB_UNARY)
00247 return 4;
00248 return 8;
00249 }
00251 virtual bool best(void) const {
00252 if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
00253 (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
00254 return true;
00255 switch (htc) {
00256 case HTC_NONE:
00257 return true;
00258 case HTC_LEX_LE:
00259 return ((x[0].val()==4) && (x[1].val()==5) &&
00260 (x[2].val()==2) && (x[3].val()==3) &&
00261 (x[4].val()==0) && (x[5].val()==1));
00262 case HTC_LEX_GR:
00263 return ((x[0].val()==5) && (x[1].val()==4) &&
00264 (x[2].val()==3) && (x[3].val()==2) &&
00265 (x[4].val()==1) && (x[5].val()==0));
00266 case HTC_BAL_LE:
00267 return ((x[0].val()==4) && (x[1].val()==5) &&
00268 (x[2].val()==2) && (x[3].val()==3) &&
00269 (x[4].val()==0) && (x[5].val()==1));
00270 case HTC_BAL_GR:
00271 return ((x[0].val()==4) && (x[1].val()==5) &&
00272 (x[2].val()==3) && (x[3].val()==2) &&
00273 (x[4].val()==0) && (x[5].val()==1));
00274 default: GECODE_NEVER;
00275 }
00276 return false;
00277 }
00279 static std::string name(void) {
00280 return "Sol";
00281 }
00283 virtual void master(unsigned long int i, const Space* _s,
00284 NoGoods&) {
00285 const HasSolutions* s = static_cast<const HasSolutions*>(_s);
00286 if (s != NULL) {
00287 BoolVarArgs b;
00288 for (int i=0; i<x.size(); i++)
00289 b << expr(*this, x[i] == s->x[i]);
00290 rel(*this, BOT_AND, b, 0);
00291 }
00292 }
00293 };
00294
00296 class Test : public Base {
00297 public:
00299 HowToBranch htb1, htb2, htb3;
00301 HowToConstrain htc;
00303 static std::string str(unsigned int i) {
00304 std::stringstream s;
00305 s << i;
00306 return s.str();
00307 }
00309 static std::string str(HowToBranch htb) {
00310 switch (htb) {
00311 case HTB_NONE: return "None";
00312 case HTB_UNARY: return "Unary";
00313 case HTB_BINARY: return "Binary";
00314 case HTB_NARY: return "Nary";
00315 default: GECODE_NEVER;
00316 }
00317 GECODE_NEVER;
00318 return "";
00319 }
00321 static std::string str(HowToConstrain htc) {
00322 switch (htc) {
00323 case HTC_NONE: return "None";
00324 case HTC_LEX_LE: return "LexLe";
00325 case HTC_LEX_GR: return "LexGr";
00326 case HTC_BAL_LE: return "BalLe";
00327 case HTC_BAL_GR: return "BalGr";
00328 default: GECODE_NEVER;
00329 }
00330 GECODE_NEVER;
00331 return "";
00332 }
00334 Test(const std::string& s,
00335 HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00336 HowToConstrain _htc=HTC_NONE)
00337 : Base("Search::"+s),
00338 htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
00339 };
00340
00342 template<class Model>
00343 class DFS : public Test {
00344 private:
00346 unsigned int c_d;
00348 unsigned int a_d;
00350 unsigned int t;
00351 public:
00353 DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00354 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00355 : Test("DFS::"+Model::name()+"::"+
00356 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00357 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00358 htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
00360 virtual bool run(void) {
00361 Model* m = new Model(htb1,htb2,htb3);
00362 Gecode::Search::FailStop f(2);
00363 Gecode::Search::Options o;
00364 o.c_d = c_d;
00365 o.a_d = a_d;
00366 o.threads = t;
00367 o.stop = &f;
00368 Gecode::DFS<Model> dfs(m,o);
00369 int n = m->solutions();
00370 delete m;
00371 while (true) {
00372 Model* s = dfs.next();
00373 if (s != NULL) {
00374 n--; delete s;
00375 }
00376 if ((s == NULL) && !dfs.stopped())
00377 break;
00378 f.limit(f.limit()+2);
00379 }
00380 return n == 0;
00381 }
00382 };
00383
00385 template<class Model>
00386 class BAB : public Test {
00387 private:
00389 unsigned int c_d;
00391 unsigned int a_d;
00393 unsigned int t;
00394 public:
00396 BAB(HowToConstrain htc,
00397 HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00398 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00399 : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
00400 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00401 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00402 htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
00404 virtual bool run(void) {
00405 Model* m = new Model(htb1,htb2,htb3,htc);
00406 Gecode::Search::FailStop f(2);
00407 Gecode::Search::Options o;
00408 o.c_d = c_d;
00409 o.a_d = a_d;
00410 o.threads = t;
00411 o.stop = &f;
00412 Gecode::BAB<Model> bab(m,o);
00413 delete m;
00414 Model* b = NULL;
00415 while (true) {
00416 Model* s = bab.next();
00417 if (s != NULL) {
00418 delete b; b=s;
00419 }
00420 if ((s == NULL) && !bab.stopped())
00421 break;
00422 f.limit(f.limit()+2);
00423 }
00424 bool ok = (b == NULL) || b->best();
00425 delete b;
00426 return ok;
00427 }
00428 };
00429
00431 template<class Model, template<class> class Engine>
00432 class RBS : public Test {
00433 private:
00435 unsigned int t;
00436 public:
00438 RBS(const std::string& e, unsigned int t0)
00439 : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
00440 HTB_BINARY,HTB_BINARY,HTB_BINARY), t(t0) {}
00442 virtual bool run(void) {
00443 Model* m = new Model(htb1,htb2,htb3);
00444 Gecode::Search::FailStop f(2);
00445 Gecode::Search::Options o;
00446 o.threads = t;
00447 o.stop = &f;
00448 o.cutoff = Gecode::Search::Cutoff::geometric(1,2);
00449 Gecode::RBS<Engine,Model> rbs(m,o);
00450 int n = m->solutions();
00451 delete m;
00452 while (true) {
00453 Model* s = rbs.next();
00454 if (s != NULL) {
00455 n--; delete s;
00456 }
00457 if ((s == NULL) && !rbs.stopped())
00458 break;
00459 f.limit(f.limit()+2);
00460 }
00461 return n == 0;
00462 }
00463 };
00464
00466 class BranchTypes {
00467 private:
00469 static const HowToBranch htbs[3];
00471 int i;
00472 public:
00474 BranchTypes(void) : i(0) {}
00476 bool operator()(void) const {
00477 return i<3;
00478 }
00480 void operator++(void) {
00481 i++;
00482 }
00484 HowToBranch htb(void) const {
00485 return htbs[i];
00486 }
00487 };
00488
00489 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
00490
00492 class ConstrainTypes {
00493 private:
00495 static const HowToConstrain htcs[4];
00497 int i;
00498 public:
00500 ConstrainTypes(void) : i(0) {}
00502 bool operator()(void) const {
00503 return i<4;
00504 }
00506 void operator++(void) {
00507 i++;
00508 }
00510 HowToConstrain htc(void) const {
00511 return htcs[i];
00512 }
00513 };
00514
00515 const HowToConstrain ConstrainTypes::htcs[4] =
00516 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
00517
00518
00520 class Create {
00521 public:
00523 Create(void) {
00524
00525 for (unsigned int t = 1; t<=4; t++)
00526 for (unsigned int c_d = 1; c_d<10; c_d++)
00527 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00528 for (BranchTypes htb1; htb1(); ++htb1)
00529 for (BranchTypes htb2; htb2(); ++htb2)
00530 for (BranchTypes htb3; htb3(); ++htb3)
00531 (void) new DFS<HasSolutions>
00532 (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
00533 new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00534 c_d, a_d, t);
00535 new DFS<SolveImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00536 c_d, a_d, t);
00537 new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
00538 c_d, a_d, t);
00539 }
00540
00541
00542 for (unsigned int t = 1; t<=4; t++)
00543 for (unsigned int c_d = 1; c_d<10; c_d++)
00544 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00545 for (ConstrainTypes htc; htc(); ++htc)
00546 for (BranchTypes htb1; htb1(); ++htb1)
00547 for (BranchTypes htb2; htb2(); ++htb2)
00548 for (BranchTypes htb3; htb3(); ++htb3) {
00549 (void) new BAB<HasSolutions>
00550 (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00551 c_d,a_d,t);
00552 }
00553 (void) new BAB<FailImmediate>
00554 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00555 (void) new BAB<SolveImmediate>
00556 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00557 (void) new BAB<HasSolutions>
00558 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00559 }
00560
00561 for (unsigned int t = 1; t<=4; t++) {
00562 (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
00563 (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
00564 (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
00565 (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
00566 (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
00567 (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
00568 }
00569 }
00570 };
00571
00572 Create c;
00573 }
00574
00575 }
00576
00577