search.cc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2008
 *
 *  Last modified:
 *     $Date: 2008-02-22 02:44:55 +0100 (Fri, 22 Feb 2008) $ by $Author: schulte $
 *     $Revision: 6273 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include "gecode/int.hh"
#include "gecode/minimodel.hh"
#include "gecode/search.hh"

#include "test/test.hh"

namespace Test { 

  namespace Search {

    using namespace Gecode;
    using namespace Gecode::Int;

    enum HowToBranch {
      HTB_NONE,   
      HTB_UNARY,  
      HTB_BINARY, 
      HTB_NARY    
    };

    enum HowToConstrain {
      HTC_NONE,   
      HTC_LEX_LE, 
      HTC_LEX_GR, 
      HTC_BAL_LE, 
      HTC_BAL_GR  
    };

    enum WhichModel {
      WM_FAIL_IMMEDIATE, 
      WM_FAIL_SEARCH,    
      WM_SOLUTIONS       
    };

    class PosValuesDesc : public BranchingDesc {
    protected:
      int _pos;
      int* _values;
    public:
      PosValuesDesc(const Branching* b, int p, IntView x)
        : BranchingDesc(b,x.size()), 
          _pos(p), 
          _values(static_cast<int*>(Memory::malloc(sizeof(int)*x.size()))) {
        ViewValues<IntView> v(x);
        int i=0;
        while (v()) {
          _values[i]=v.val(); ++i; ++v;
        }
      }
      int pos(void) const {
        return _pos;
      }
      int val(unsigned int a) const {
        return _values[a];
      }
      virtual size_t size(void) const {
        return 0;
      }
      virtual ~PosValuesDesc(void) {
        Memory::free(_values);
      }
    };


    class NaryBranching : public Branching {
    protected:
      ViewArray<IntView> x; 
      NaryBranching(Space* home, bool share, NaryBranching& b) 
        : Branching(home,share,b) {
        x.update(home,share,b.x);
      }
    public:
      NaryBranching(Space* home, ViewArray<IntView>& x0) 
        : Branching(home), x(x0) {}
      virtual Actor* copy(Space* home, bool share) {
        return new (home) NaryBranching(home,share,*this);
      }
      virtual bool status(const Space*) const {
        for (int i=0; i<x.size(); i++)
          if (!x[i].assigned())
            return true;
        return false;
      }
      virtual const BranchingDesc* description(const Space*) const {
        int i=0; 
        while (x[i].assigned()) 
          i++;
        return new PosValuesDesc(this,i,x[i]);
      }
      virtual ExecStatus commit(Space* home, const BranchingDesc* d,
                                unsigned int a) {
        const PosValuesDesc* pvd = static_cast<const PosValuesDesc*>(d);
        return me_failed(x[pvd->pos()].eq(home,pvd->val(a)))
          ? ES_FAILED : ES_OK;
      }
      static Support::Symbol ati(void) {
        return "Test::Search::NaryBranching";
      }
      virtual Reflection::ActorSpec spec(Space* home, Reflection::VarMap& m) {
        Reflection::ActorSpec s(ati());
        return s << x.spec(home, m);
      }

      virtual Reflection::BranchingSpec branchingSpec(Space*, 
                                                      Reflection::VarMap&,
                                                      const BranchingDesc* d) {
        Reflection::BranchingSpec bs(d);
        return bs;
      }
      static void post(Space*, Reflection::VarMap&,
                       const Reflection::ActorSpec&) {
      }
    };

    class TestSpace : public Space {
    public:
      TestSpace(void) {}
      TestSpace(bool share, TestSpace& s) : Space(share,s) {}
      virtual int solutions(void) const = 0;
      virtual bool best(void) const = 0;
    };

    class FailImmediate : public TestSpace {
    public:
      IntVarArray x;
      FailImmediate(HowToBranch, HowToBranch, HowToBranch, 
                    HowToConstrain=HTC_NONE) 
        : x(this,1,0,0) {
        rel(this, x[0], IRT_EQ, 1);
      }
      FailImmediate(bool share, FailImmediate& s) : TestSpace(share,s) {
        x.update(this, share, s.x);
      }
      virtual Space* copy(bool share) {
        return new FailImmediate(share,*this);
      }
      void constrain(Space*) {
      }
      virtual int solutions(void) const {
        return 0;
      }
      virtual bool best(void) const {
        return false;
      }
      static std::string name(void) {
        return "Fail";
      }
    };

    class HasSolutions : public TestSpace {
    public:
      IntVarArray x;
      HowToBranch htb1, htb2, htb3;
      HowToConstrain htc;
      void branch(const IntVarArgs& x, HowToBranch htb) {
        switch (htb) {
        case HTB_NONE:
          break;
        case HTB_UNARY:
          assign(this, x, INT_ASSIGN_MIN);
          break;
        case HTB_BINARY:
          Gecode::branch(this, x, INT_VAR_NONE, INT_VAL_MIN);
          break;
        case HTB_NARY:
          {
            ViewArray<IntView> xv(this,x);
            new (this) NaryBranching(this, xv);
            break;
          }
        }
      }
      HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
                   HowToConstrain _htc=HTC_NONE) 
        : x(this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
        distinct(this, x);
        rel(this, x[2], IRT_LQ, 3); rel(this, x[3], IRT_LQ, 3);
        rel(this, x[4], IRT_LQ, 1); rel(this, x[5], IRT_LQ, 1);
        IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
        IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
        IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
      }
      HasSolutions(bool share, HasSolutions& s) 
        : TestSpace(share,s), 
          htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
        x.update(this, share, s.x);
      }
      virtual Space* copy(bool share) {
        return new HasSolutions(share,*this);
      }
      void constrain(Space* _s) {
        HasSolutions* s = static_cast<HasSolutions*>(_s);
        switch (htc) {
        case HTC_NONE:
          break;
        case HTC_LEX_LE:
        case HTC_LEX_GR:
          {
            IntVarArgs y(6);
            for (int i=0; i<6; i++)
              y[i].init(this, s->x[i].val(), s->x[i].val());
            lex(this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
            break;
          }
        case HTC_BAL_LE:
        case HTC_BAL_GR:
          {
            IntVarArgs y(6);
            for (int i=0; i<6; i++)
              y[i].init(this, s->x[i].val(), s->x[i].val());
            IntVar xs(this, -18, 18);
            IntVar ys(this, -18, 18);
            post(this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
            post(this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
            rel(this, 
                abs(this,xs), 
                (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
                abs(this,ys));
            break;
          }
        }
      }
      virtual int solutions(void) const {
        if (htb1 == HTB_NONE) {
          assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
          return 1;
        }
        if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
          return 0;
        if (htb3 == HTB_UNARY)
          return 4;
        return 8;
      }
      virtual bool best(void) const {
        if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
            (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
          return true;
        switch (htc) {
        case HTC_NONE: 
          return true;
        case HTC_LEX_LE:
          return ((x[0].val()==4) && (x[1].val()==5) &&
                  (x[2].val()==2) && (x[3].val()==3) && 
                  (x[4].val()==0) && (x[5].val()==1));
        case HTC_LEX_GR:
          return ((x[0].val()==5) && (x[1].val()==4) &&
                  (x[2].val()==3) && (x[3].val()==2) &&
                  (x[4].val()==1) && (x[5].val()==0));
        case HTC_BAL_LE:
          return ((x[0].val()==4) && (x[1].val()==5) &&
                  (x[2].val()==2) && (x[3].val()==3) && 
                  (x[4].val()==0) && (x[5].val()==1));
        case HTC_BAL_GR:
          return ((x[0].val()==4) && (x[1].val()==5) &&
                  (x[2].val()==3) && (x[3].val()==2) &&
                  (x[4].val()==0) && (x[5].val()==1));
        default: GECODE_NEVER;
        }
        return false;
      }
      static std::string name(void) {
        return "Sol";
      }
    };

    class Test : public Base {
    public:
      HowToBranch htb1, htb2, htb3;
      HowToConstrain htc;
      static std::string str(unsigned int i) {
        std::stringstream s;
        s << i;
        return s.str();
      }
      static std::string str(HowToBranch htb) {
        switch (htb) {
        case HTB_NONE:   return "None";
        case HTB_UNARY:  return "Unary";
        case HTB_BINARY: return "Binary";
        case HTB_NARY:   return "Nary";
        default: GECODE_NEVER;
        }
        GECODE_NEVER;
        return "";
      }
      static std::string str(HowToConstrain htc) {
        switch (htc) {
        case HTC_NONE:   return "None";
        case HTC_LEX_LE: return "LexLe";
        case HTC_LEX_GR: return "LexGr";
        case HTC_BAL_LE: return "BalLe";
        case HTC_BAL_GR: return "BalGr";
        default: GECODE_NEVER;
        }
        GECODE_NEVER;
        return "";
      }
      Test(const std::string& s,
           HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
           HowToConstrain _htc=HTC_NONE) 
        : Base("Search::"+s), 
          htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
    };

    template <class Model>
    class DFS : public Test {
    private:
      unsigned int c_d;
      unsigned int a_d;
    public:
      DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
          unsigned int c_d0, unsigned int a_d0) 
        : Test("DFS::"+Model::name()+"::"+
               str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
               str(c_d0)+"::"+str(a_d0),
               htb1,htb2,htb3), c_d(c_d0), a_d(a_d0) {}
      virtual bool run(void) {
        Model* m = new Model(htb1,htb2,htb3);
        Gecode::Search::FailStop f(2);
        Gecode::Search::Options o;
        o.c_d  = c_d;
        o.a_d  = a_d;
        o.stop = &f;
        Gecode::DFS<Model> dfs(m,o);
        int n = m->solutions();
        delete m;
        while (true) {
          Model* s = dfs.next();
          if (s != NULL) {
            n--; delete s;
          }
          if ((s == NULL) && !dfs.stopped())
            break;
          f.limit(f.limit()+2);
        }
        return n == 0;
      }
    };

    template <class Model>
    class LDS : public Test {
    public:
      LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3)
        : Test("LDS::"+Model::name()+"::"+
               str(htb1)+"::"+str(htb2)+"::"+str(htb3),
               htb1,htb2,htb3) {}
      virtual bool run(void) {
        Model* m = new Model(htb1,htb2,htb3);
        Gecode::Search::FailStop f(2);
        Gecode::Search::Options o;
        o.stop = &f;
        Gecode::LDS<Model> lds(m,50,o);
        int n = m->solutions();
        delete m;
        while (true) {
          Model* s = lds.next();
          if (s != NULL) {
            n--; delete s;
          }
          if ((s == NULL) && !lds.stopped())
            break;
          f.limit(f.limit()+2);
        }
        return n == 0;
      }
    };

    template <class Model, template<class> class Engine>
    class Best : public Test {
    private:
      unsigned int c_d;
      unsigned int a_d;
    public:
      Best(const std::string& b, HowToConstrain htc,
           HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
           unsigned int c_d0, unsigned int a_d0) 
        : Test(b+"::"+Model::name()+"::"+str(htc)+"::"+
               str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
               str(c_d0)+"::"+str(a_d0),
               htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0) {}
      virtual bool run(void) {
        Model* m = new Model(htb1,htb2,htb3,htc);
        Gecode::Search::FailStop f(2);
        Gecode::Search::Options o;
        o.c_d  = c_d;
        o.a_d  = a_d;
        o.stop = &f;
        Engine<Model> best(m,o);
        delete m;
        Model* b = NULL;
        while (true) {
          Model* s = best.next();
          if (s != NULL) {
            delete b; b=s;
          }
          if ((s == NULL) && !best.stopped())
            break;
          f.limit(f.limit()+2);
        }
        bool ok = (b == NULL) || b->best();
        delete b;
        return ok;
      }
    };

    class BranchTypes {
    private:
      static const HowToBranch htbs[3];
      int i; 
    public:
      BranchTypes(void) : i(0) {}
      bool operator()(void) const {
        return i<3;
      } 
      void operator++(void) {
        i++;
      }
      HowToBranch htb(void) const {
        return htbs[i];
      }
    };

    const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
    
    class ConstrainTypes {
    private:
      static const HowToConstrain htcs[4];
      int i; 
    public:
      ConstrainTypes(void) : i(0) {}
      bool operator()(void) const {
        return i<4;
      } 
      void operator++(void) {
        i++;
      }
      HowToConstrain htc(void) const {
        return htcs[i];
      }
    };

    const HowToConstrain ConstrainTypes::htcs[4] = 
      {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
    

    class Create {
    public:
      Create(void) {
        // Depth-first search
        for (unsigned int c_d = 1; c_d<10; c_d++)
          for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
            for (BranchTypes htb1; htb1(); ++htb1)
              for (BranchTypes htb2; htb2(); ++htb2)
                for (BranchTypes htb3; htb3(); ++htb3)
                  (void) new DFS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb(),
                                               c_d, a_d);
            new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE, c_d, a_d);
            new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE, c_d, a_d);
          }

        // Limited discrepancy search
        for (BranchTypes htb1; htb1(); ++htb1)
          for (BranchTypes htb2; htb2(); ++htb2)
            for (BranchTypes htb3; htb3(); ++htb3)
              (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb());
        new LDS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE);
        new LDS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE);

        // Best solution search
        for (unsigned int c_d = 1; c_d<10; c_d++)
          for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
            for (ConstrainTypes htc; htc(); ++htc)
              for (BranchTypes htb1; htb1(); ++htb1)
                for (BranchTypes htb2; htb2(); ++htb2)
                  for (BranchTypes htb3; htb3(); ++htb3) {
                    (void) new Best<HasSolutions,BAB>
                      ("BAB",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),c_d,a_d);
                    (void) new Best<HasSolutions,Restart>
                      ("Restart",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),c_d,a_d);
                  }
            (void) new Best<FailImmediate,BAB>
              ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d);
            (void) new Best<HasSolutions,BAB>
              ("BAB",HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d);
          }

      }
    };

    Create c;
  }

}

// STATISTICS: test-search