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] = IntVar(*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] = IntVar(*this, s.x[i].val(), s.x[i].val());
00191 IntVar xs(*this, -18, 18);
00192 IntVar ys(*this, -18, 18);
00193 rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
00194 rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
00195 rel(*this,
00196 expr(*this,abs(xs)),
00197 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
00198 expr(*this,abs(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, template<class> class Engine>
00340 class Best : public Test {
00341 private:
00343 unsigned int c_d;
00345 unsigned int a_d;
00347 unsigned int t;
00348 public:
00350 Best(const std::string& b, HowToConstrain htc,
00351 HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00352 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00353 : Test(b+"::"+Model::name()+"::"+str(htc)+"::"+
00354 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00355 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00356 htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
00358 virtual bool run(void) {
00359 Model* m = new Model(htb1,htb2,htb3,htc);
00360 Gecode::Search::FailStop f(2);
00361 Gecode::Search::Options o;
00362 o.c_d = c_d;
00363 o.a_d = a_d;
00364 o.threads = t;
00365 o.stop = &f;
00366 Engine<Model> best(m,o);
00367 delete m;
00368 Model* b = NULL;
00369 while (true) {
00370 Model* s = best.next();
00371 if (s != NULL) {
00372 delete b; b=s;
00373 }
00374 if ((s == NULL) && !best.stopped())
00375 break;
00376 f.limit(f.limit()+2);
00377 }
00378 bool ok = (b == NULL) || b->best();
00379 delete b;
00380 return ok;
00381 }
00382 };
00383
00385 class BranchTypes {
00386 private:
00388 static const HowToBranch htbs[3];
00390 int i;
00391 public:
00393 BranchTypes(void) : i(0) {}
00395 bool operator()(void) const {
00396 return i<3;
00397 }
00399 void operator++(void) {
00400 i++;
00401 }
00403 HowToBranch htb(void) const {
00404 return htbs[i];
00405 }
00406 };
00407
00408 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
00409
00411 class ConstrainTypes {
00412 private:
00414 static const HowToConstrain htcs[4];
00416 int i;
00417 public:
00419 ConstrainTypes(void) : i(0) {}
00421 bool operator()(void) const {
00422 return i<4;
00423 }
00425 void operator++(void) {
00426 i++;
00427 }
00429 HowToConstrain htc(void) const {
00430 return htcs[i];
00431 }
00432 };
00433
00434 const HowToConstrain ConstrainTypes::htcs[4] =
00435 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
00436
00437
00439 class Create {
00440 public:
00442 Create(void) {
00443
00444 for (unsigned int t = 1; t<=4; t++)
00445 for (unsigned int c_d = 1; c_d<10; c_d++)
00446 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00447 for (BranchTypes htb1; htb1(); ++htb1)
00448 for (BranchTypes htb2; htb2(); ++htb2)
00449 for (BranchTypes htb3; htb3(); ++htb3)
00450 (void) new DFS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb(),
00451 c_d, a_d, t);
00452 new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00453 c_d, a_d, t);
00454 new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
00455 c_d, a_d, t);
00456 }
00457
00458
00459 for (unsigned int t = 1; t<=4; t++)
00460 for (unsigned int c_d = 1; c_d<10; c_d++)
00461 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00462 for (ConstrainTypes htc; htc(); ++htc)
00463 for (BranchTypes htb1; htb1(); ++htb1)
00464 for (BranchTypes htb2; htb2(); ++htb2)
00465 for (BranchTypes htb3; htb3(); ++htb3) {
00466 (void) new Best<HasSolutions,BAB>
00467 ("BAB",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00468 c_d,a_d,t);
00469 (void) new Best<HasSolutions,Restart>
00470 ("Restart",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00471 c_d,a_d,t);
00472 }
00473 (void) new Best<FailImmediate,BAB>
00474 ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00475 (void) new Best<HasSolutions,BAB>
00476 ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00477 }
00478
00479 }
00480 };
00481
00482 Create c;
00483 }
00484
00485 }
00486
00487