Generated on Thu Apr 11 13:59:22 2019 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/minimodel.hh>
00035 #include <gecode/search.hh>
00036 
00037 #include "test/test.hh"
00038 
00039 namespace Test {
00040 
00042   namespace Search {
00043 
00044     using namespace Gecode;
00045     using namespace Gecode::Int;
00046 
00048     enum HowToBranch {
00049       HTB_NONE,   
00050       HTB_UNARY,  
00051       HTB_BINARY, 
00052       HTB_NARY    
00053     };
00054 
00056     enum HowToConstrain {
00057       HTC_NONE,   
00058       HTC_LEX_LE, 
00059       HTC_LEX_GR, 
00060       HTC_BAL_LE, 
00061       HTC_BAL_GR  
00062     };
00063 
00065     enum WhichModel {
00066       WM_FAIL_IMMEDIATE, 
00067       WM_FAIL_SEARCH,    
00068       WM_SOLUTIONS       
00069     };
00070 
00072     class TestSpace : public Space {
00073     public:
00075       TestSpace(void) {}
00077       TestSpace(TestSpace& s) : Space(s) {}
00079       virtual int solutions(void) const = 0;
00081       virtual bool best(void) const = 0;
00083       virtual bool master(const MetaInfo& mi) {
00084         if (mi.type() == MetaInfo::RESTART) {
00085           if (mi.last() != NULL)
00086             constrain(*mi.last());
00087           return false;
00088         } else {
00089           return false;
00090         }
00091       }
00092     };
00093 
00095     class FailImmediate : public TestSpace {
00096     public:
00098       IntVarArray x;
00100       FailImmediate(HowToBranch, HowToBranch, HowToBranch,
00101                     HowToConstrain=HTC_NONE)
00102         : x(*this,1,0,0) {
00103         rel(*this, x[0], IRT_EQ, 1);
00104       }
00106       FailImmediate(FailImmediate& s) : TestSpace(s) {
00107         x.update(*this, s.x);
00108       }
00110       virtual Space* copy(void) {
00111         return new FailImmediate(*this);
00112       }
00114       virtual void constrain(const Space&) {
00115       }
00117       virtual int solutions(void) const {
00118         return 0;
00119       }
00121       virtual bool best(void) const {
00122         return false;
00123       }
00125       static std::string name(void) {
00126         return "Fail";
00127       }
00128     };
00129 
00131     class SolveImmediate : public TestSpace {
00132     public:
00134       IntVarArray x;
00136       SolveImmediate(HowToBranch, HowToBranch, HowToBranch,
00137                      HowToConstrain=HTC_NONE)
00138         : x(*this,1,0,0) {}
00140       SolveImmediate(SolveImmediate& s) : TestSpace(s) {
00141         x.update(*this, s.x);
00142       }
00144       virtual Space* copy(void) {
00145         return new SolveImmediate(*this);
00146       }
00148       virtual void constrain(const Space&) {
00149         fail();
00150       }
00152       virtual int solutions(void) const {
00153         return 1;
00154       }
00156       virtual bool best(void) const {
00157         return true;
00158       }
00160       static std::string name(void) {
00161         return "Solve";
00162       }
00163     };
00164 
00166     class HasSolutions : public TestSpace {
00167     public:
00169       IntVarArray x;
00171       HowToBranch htb1, htb2, htb3;
00173       HowToConstrain htc;
00175       void branch(const IntVarArgs& x, HowToBranch htb) {
00176         switch (htb) {
00177         case HTB_NONE:
00178           break;
00179         case HTB_UNARY:
00180           assign(*this, x, INT_ASSIGN_MIN());
00181           break;
00182         case HTB_BINARY:
00183           Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
00184           break;
00185         case HTB_NARY:
00186           Gecode::branch(*this, x, INT_VAR_NONE(), INT_VALUES_MIN());
00187           break;
00188         }
00189       }
00191       HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00192                    HowToConstrain _htc=HTC_NONE)
00193         : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
00194         distinct(*this, x);
00195         rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
00196         rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
00197         IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
00198         IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
00199         IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
00200       }
00202       HasSolutions(HasSolutions& s)
00203         : TestSpace(s),
00204           htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
00205         x.update(*this, s.x);
00206       }
00208       virtual Space* copy(void) {
00209         return new HasSolutions(*this);
00210       }
00212       virtual void constrain(const Space& _s) {
00213         const HasSolutions& s = static_cast<const HasSolutions&>(_s);
00214         switch (htc) {
00215         case HTC_NONE:
00216           break;
00217         case HTC_LEX_LE:
00218         case HTC_LEX_GR:
00219           {
00220             IntVarArgs y(6);
00221             for (int i=0; i<6; i++)
00222               y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
00223             lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
00224             break;
00225           }
00226         case HTC_BAL_LE:
00227         case HTC_BAL_GR:
00228           {
00229             IntVarArgs y(6);
00230             for (int i=0; i<6; i++)
00231               y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
00232             IntVar xs(*this, -18, 18);
00233             IntVar ys(*this, -18, 18);
00234             rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
00235             rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
00236             rel(*this,
00237                 expr(*this,abs(xs)),
00238                 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
00239                 expr(*this,abs(ys)));
00240             break;
00241           }
00242         }
00243       }
00245       virtual int solutions(void) const {
00246         if (htb1 == HTB_NONE) {
00247           assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
00248           return 1;
00249         }
00250         if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
00251           return 0;
00252         if (htb3 == HTB_UNARY)
00253           return 4;
00254         return 8;
00255       }
00257       virtual bool best(void) const {
00258         if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
00259             (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
00260           return true;
00261         switch (htc) {
00262         case HTC_NONE:
00263           return true;
00264         case HTC_LEX_LE:
00265           return ((x[0].val()==4) && (x[1].val()==5) &&
00266                   (x[2].val()==2) && (x[3].val()==3) &&
00267                   (x[4].val()==0) && (x[5].val()==1));
00268         case HTC_LEX_GR:
00269           return ((x[0].val()==5) && (x[1].val()==4) &&
00270                   (x[2].val()==3) && (x[3].val()==2) &&
00271                   (x[4].val()==1) && (x[5].val()==0));
00272         case HTC_BAL_LE:
00273           return ((x[0].val()==4) && (x[1].val()==5) &&
00274                   (x[2].val()==2) && (x[3].val()==3) &&
00275                   (x[4].val()==0) && (x[5].val()==1));
00276         case HTC_BAL_GR:
00277           return ((x[0].val()==4) && (x[1].val()==5) &&
00278                   (x[2].val()==3) && (x[3].val()==2) &&
00279                   (x[4].val()==0) && (x[5].val()==1));
00280         default: GECODE_NEVER;
00281         }
00282         return false;
00283       }
00285       static std::string name(void) {
00286         return "Sol";
00287       }
00289       virtual bool master(const MetaInfo& mi) {
00290         switch (mi.type()) {
00291         case MetaInfo::RESTART:
00292           if (mi.last() != NULL) {
00293             const HasSolutions* s
00294               = static_cast<const HasSolutions*>(mi.last());
00295             BoolVarArgs b;
00296             for (int i=0; i<x.size(); i++)
00297               b << expr(*this, x[i] == s->x[i]);
00298             rel(*this, BOT_AND, b, 0);
00299           }
00300           break;
00301         case MetaInfo::PORTFOLIO:
00302           // Do not kill the brancher!
00303           break;
00304         default:
00305           break;
00306         }
00307         return false;
00308       }
00309     };
00310 
00312     class Test : public Base {
00313     public:
00315       HowToBranch htb1, htb2, htb3;
00317       HowToConstrain htc;
00319       static std::string str(unsigned int i) {
00320         std::stringstream s;
00321         s << i;
00322         return s.str();
00323       }
00325       static std::string str(HowToBranch htb) {
00326         switch (htb) {
00327         case HTB_NONE:   return "None";
00328         case HTB_UNARY:  return "Unary";
00329         case HTB_BINARY: return "Binary";
00330         case HTB_NARY:   return "Nary";
00331         default: GECODE_NEVER;
00332         }
00333         GECODE_NEVER;
00334         return "";
00335       }
00337       static std::string str(HowToConstrain htc) {
00338         switch (htc) {
00339         case HTC_NONE:   return "None";
00340         case HTC_LEX_LE: return "LexLe";
00341         case HTC_LEX_GR: return "LexGr";
00342         case HTC_BAL_LE: return "BalLe";
00343         case HTC_BAL_GR: return "BalGr";
00344         default: GECODE_NEVER;
00345         }
00346         GECODE_NEVER;
00347         return "";
00348       }
00350       Test(const std::string& s,
00351            HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
00352            HowToConstrain _htc=HTC_NONE)
00353         : Base("Search::"+s),
00354           htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
00355     };
00356 
00358     template<class Model>
00359     class DFS : public Test {
00360     private:
00362       unsigned int c_d;
00364       unsigned int a_d;
00366       unsigned int t;
00367     public:
00369       DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00370           unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00371         : Test("DFS::"+Model::name()+"::"+
00372                str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00373                str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00374                htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
00376       virtual bool run(void) {
00377         Model* m = new Model(htb1,htb2,htb3);
00378         Gecode::Search::FailStop f(2);
00379         Gecode::Search::Options o;
00380         o.c_d = c_d;
00381         o.a_d = a_d;
00382         o.threads = t;
00383         o.stop = &f;
00384         Gecode::DFS<Model> dfs(m,o);
00385         int n = m->solutions();
00386         delete m;
00387         while (true) {
00388           Model* s = dfs.next();
00389           if (s != NULL) {
00390             n--; delete s;
00391           }
00392           if ((s == NULL) && !dfs.stopped())
00393             break;
00394           f.limit(f.limit()+2);
00395         }
00396         return n == 0;
00397       }
00398     };
00399 
00401     template<class Model>
00402     class LDS : public Test {
00403     private:
00405       unsigned int t;
00406     public:
00408       LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00409           unsigned int t0)
00410         : Test("LDS::"+Model::name()+"::"+
00411                str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
00412                htb1,htb2,htb3), t(t0) {}
00414       virtual bool run(void) {
00415         Model* m = new Model(htb1,htb2,htb3);
00416         Gecode::Search::FailStop f(2);
00417         Gecode::Search::Options o;
00418         o.threads = t;
00419         o.d_l = 50;
00420         o.stop = &f;
00421         Gecode::LDS<Model> lds(m,o);
00422         int n = m->solutions();
00423         delete m;
00424         while (true) {
00425           Model* s = lds.next();
00426           if (s != NULL) {
00427             n--; delete s;
00428           }
00429           if ((s == NULL) && !lds.stopped())
00430             break;
00431           f.limit(f.limit()+2);
00432         }
00433         return n == 0;
00434       }
00435     };
00436 
00438     template<class Model>
00439     class BAB : public Test {
00440     private:
00442       unsigned int c_d;
00444       unsigned int a_d;
00446       unsigned int t;
00447     public:
00449       BAB(HowToConstrain htc,
00450           HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
00451           unsigned int c_d0, unsigned int a_d0, unsigned int t0)
00452         : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
00453                str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
00454                str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
00455                htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
00457       virtual bool run(void) {
00458         Model* m = new Model(htb1,htb2,htb3,htc);
00459         Gecode::Search::FailStop f(2);
00460         Gecode::Search::Options o;
00461         o.c_d = c_d;
00462         o.a_d = a_d;
00463         o.threads = t;
00464         o.stop = &f;
00465         Gecode::BAB<Model> bab(m,o);
00466         delete m;
00467         Model* b = NULL;
00468         while (true) {
00469           Model* s = bab.next();
00470           if (s != NULL) {
00471             delete b; b=s;
00472           }
00473           if ((s == NULL) && !bab.stopped())
00474             break;
00475           f.limit(f.limit()+2);
00476         }
00477         bool ok = (b == NULL) || b->best();
00478         delete b;
00479         return ok;
00480       }
00481     };
00482 
00484     template<class Model, template<class> class Engine>
00485     class RBS : public Test {
00486     private:
00488       unsigned int t;
00489     public:
00491       RBS(const std::string& e, unsigned int t0)
00492         : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
00493                HTB_BINARY,HTB_BINARY,HTB_BINARY), t(t0) {}
00495       virtual bool run(void) {
00496         Model* m = new Model(htb1,htb2,htb3);
00497         Gecode::Search::FailStop f(2);
00498         Gecode::Search::Options o;
00499         o.threads = t;
00500         o.stop = &f;
00501         o.d_l = 100;
00502         o.cutoff = Gecode::Search::Cutoff::geometric(1,2);
00503         Gecode::RBS<Model,Engine> rbs(m,o);
00504         int n = m->solutions();
00505         delete m;
00506         while (true) {
00507           Model* s = rbs.next();
00508           if (s != NULL) {
00509             n--; delete s;
00510           }
00511           if ((s == NULL) && !rbs.stopped())
00512             break;
00513           f.limit(f.limit()+2);
00514         }
00515         return n == 0;
00516       }
00517     };
00518 
00520     template<class Model, template<class> class Engine>
00521     class PBS : public Test {
00522     private:
00524       bool best;
00526       unsigned int a;
00528       unsigned int t;
00529     public:
00531       PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
00532         : Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
00533                HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
00535       virtual bool run(void) {
00536         Model* m = new Model(htb1,htb2,htb3);
00537         Gecode::Search::FailStop f(2);
00538         Gecode::Search::Options o;
00539         o.assets = a;
00540         o.threads = t;
00541         o.d_l = 100;
00542         o.stop = &f;
00543         Gecode::PBS<Model,Engine> pbs(m,o);
00544         if (best) {
00545           Model* b = NULL;
00546           while (true) {
00547             Model* s = pbs.next();
00548             if (s != NULL) {
00549               delete b; b=s;
00550             }
00551             if ((s == NULL) && !pbs.stopped())
00552               break;
00553             f.limit(f.limit()+2);
00554           }
00555           bool ok = (b == NULL) || b->best();
00556           delete b;
00557           return ok;
00558         } else {
00559           int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
00560           delete m;
00561           while (true) {
00562             Model* s = pbs.next();
00563             if (s != NULL) {
00564               n--; delete s;
00565             }
00566             if ((s == NULL) && !pbs.stopped())
00567               break;
00568             f.limit(f.limit()+2);
00569           }
00570           return n >= 0;
00571         }
00572       }
00573     };
00574 
00576     template<class Model>
00577     class SEBPBS : public Test {
00578     private:
00580       bool best;
00582       unsigned int mt;
00584       unsigned int st;
00585     public:
00587       SEBPBS(const std::string& e, bool b, unsigned int mt0, unsigned int st0)
00588         : Test("PBS::SEB::"+e+"::"+Model::name()+"::"+str(mt0)+"::"+str(st0),
00589                HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
00591       virtual bool run(void) {
00592         using namespace Gecode;
00593         Model* m = new Model(htb1,htb2,htb3);
00594         Gecode::Search::FailStop f(2);
00595 
00596         Gecode::Search::Options mo;
00597         mo.threads = mt;
00598         mo.d_l = 100;
00599         mo.stop = &f;
00600 
00601         Gecode::Search::Options so;
00602         so.threads = st;
00603         so.d_l = 100;
00604         so.cutoff = Gecode::Search::Cutoff::constant(1000000);
00605         if (best) {
00606           SEBs sebs(3);
00607           sebs[0] = bab<Model>(so);
00608           sebs[1] = bab<Model>(so);
00609           sebs[2] = rbs<Model,Gecode::BAB>(so);
00610           Gecode::PBS<Model,Gecode::BAB> pbs(m, sebs, mo);
00611           delete m;
00612 
00613           Model* b = NULL;
00614           while (true) {
00615             Model* s = pbs.next();
00616             if (s != NULL) {
00617               delete b; b=s;
00618             }
00619             if ((s == NULL) && !pbs.stopped())
00620               break;
00621             f.limit(f.limit()+2);
00622           }
00623           bool ok = (b == NULL) || b->best();
00624           delete b;
00625           return ok;
00626         } else {
00627           SEBs sebs(3);
00628           sebs[0] = dfs<Model>(so);
00629           sebs[1] = lds<Model>(so);
00630           sebs[2] = rbs<Model,Gecode::DFS>(so);
00631           Gecode::PBS<Model,Gecode::DFS> pbs(m, sebs, mo);
00632 
00633           int n = 3 * m->solutions();
00634           delete m;
00635 
00636           while (true) {
00637             Model* s = pbs.next();
00638             if (s != NULL) {
00639               n--; delete s;
00640             }
00641             if ((s == NULL) && !pbs.stopped())
00642               break;
00643             f.limit(f.limit()+2);
00644           }
00645           return n >= 0;
00646         }
00647       }
00648     };
00649 
00651     class BranchTypes {
00652     private:
00654       static const HowToBranch htbs[3];
00656       int i;
00657     public:
00659       BranchTypes(void) : i(0) {}
00661       bool operator()(void) const {
00662         return i<3;
00663       }
00665       void operator++(void) {
00666         i++;
00667       }
00669       HowToBranch htb(void) const {
00670         return htbs[i];
00671       }
00672     };
00673 
00674     const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
00675 
00677     class ConstrainTypes {
00678     private:
00680       static const HowToConstrain htcs[4];
00682       int i;
00683     public:
00685       ConstrainTypes(void) : i(0) {}
00687       bool operator()(void) const {
00688         return i<4;
00689       }
00691       void operator++(void) {
00692         i++;
00693       }
00695       HowToConstrain htc(void) const {
00696         return htcs[i];
00697       }
00698     };
00699 
00700     const HowToConstrain ConstrainTypes::htcs[4] =
00701       {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
00702 
00703 
00705     class Create {
00706     public:
00708       Create(void) {
00709         // Depth-first search
00710         for (unsigned int t = 1; t<=4; t++)
00711           for (unsigned int c_d = 1; c_d<10; c_d++)
00712             for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00713               for (BranchTypes htb1; htb1(); ++htb1)
00714                 for (BranchTypes htb2; htb2(); ++htb2)
00715                   for (BranchTypes htb3; htb3(); ++htb3)
00716                     (void) new DFS<HasSolutions>
00717                       (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
00718               new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00719                                      c_d, a_d, t);
00720               new DFS<SolveImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
00721                                       c_d, a_d, t);
00722               new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
00723                                     c_d, a_d, t);
00724             }
00725 
00726         // Limited discrepancy search
00727         for (unsigned int t = 1; t<=4; t++) {
00728           for (BranchTypes htb1; htb1(); ++htb1)
00729             for (BranchTypes htb2; htb2(); ++htb2)
00730               for (BranchTypes htb3; htb3(); ++htb3)
00731                 (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
00732                                              ,t);
00733           new LDS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE, t);
00734           new LDS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE, t);
00735         }
00736 
00737         // Best solution search
00738         for (unsigned int t = 1; t<=4; t++)
00739           for (unsigned int c_d = 1; c_d<10; c_d++)
00740             for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
00741               for (ConstrainTypes htc; htc(); ++htc)
00742                 for (BranchTypes htb1; htb1(); ++htb1)
00743                   for (BranchTypes htb2; htb2(); ++htb2)
00744                     for (BranchTypes htb3; htb3(); ++htb3) {
00745                       (void) new BAB<HasSolutions>
00746                         (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
00747                          c_d,a_d,t);
00748                   }
00749               (void) new BAB<FailImmediate>
00750                 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00751               (void) new BAB<SolveImmediate>
00752                 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00753               (void) new BAB<HasSolutions>
00754                 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
00755             }
00756         // Restart-based search
00757         for (unsigned int t=1; t<=4; t++) {
00758           (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
00759           (void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
00760           (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
00761           (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
00762           (void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
00763           (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
00764           (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
00765           (void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
00766           (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
00767         }
00768         // Portfolio-based search
00769         for (unsigned int a=1; a<=4; a++)
00770           for (unsigned int t=1; t<=2*a; t++) {
00771             (void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
00772             (void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
00773             (void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
00774             (void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
00775             (void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
00776             (void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
00777             (void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
00778             (void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
00779             (void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
00780           }
00781         // Portfolio-based search using SEBs
00782         for (unsigned int mt=1; mt<=3; mt += 2)
00783           for (unsigned int st=1; st<=8; st++) {
00784             (void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
00785             (void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
00786             (void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
00787             (void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
00788             (void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
00789             (void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
00790           }
00791       }
00792     };
00793 
00794     Create c;
00795   }
00796 
00797 }
00798 
00799 // STATISTICS: test-search