Generated on Wed Nov 5 2014 05:18:33 for Gecode by doxygen 1.7.6.1
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: 2013-07-15 12:02:18 +0200 (Mon, 15 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13880 $
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 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         // Depth-first search
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         // Best solution search
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         // Restart-based search
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 // STATISTICS: test-search