search.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-04 16:13:00 +0200 (Fri, 04 Jun 2010) $ by $Author: schulte $ 00011 * $Revision: 11028 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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> 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 // Depth-first search 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 // Limited discrepancy search 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 // Best solution search 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 // STATISTICS: test-search