search.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.dev>
 *     Guido Tack <tack@gecode.dev>
 *
 *  Contributing authors:
 *     Kevin Leo <kevin.leo@monash.edu>
 *     Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
 *     Maxim Shishmarev <maxim.shishmarev@monash.edu>
 *
 *  Copyright:
 *     Kevin Leo, 2017
 *     Christian Schulte, 2002
 *     Mikael Zayenz Lagerkvist, 2026
 *     Maxim Shishmarev, 2017
 *     Guido Tack, 2004
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  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.
 *
 */
 
#ifndef GECODE_SEARCH_HH
#define GECODE_SEARCH_HH
 
#include <chrono>
#include <initializer_list>
#include <atomic>
 
#include <gecode/kernel.hh>
 
/*
 * Configure linking
 *
 */
#if !defined(GECODE_STATIC_LIBS) && \
    (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
 
#ifdef GECODE_BUILD_SEARCH
#define GECODE_SEARCH_EXPORT __declspec( dllexport )
#else
#define GECODE_SEARCH_EXPORT __declspec( dllimport )
#endif
 
#else
 
#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
#else
#define GECODE_SEARCH_EXPORT
#endif
 
#endif
 
// Configure auto-linking
#ifndef GECODE_BUILD_SEARCH
#define GECODE_LIBRARY_NAME "Search"
#include <gecode/support/auto-link.hpp>
#endif
 
 
namespace Gecode { namespace Search {

  namespace Sequential {}

  namespace Parallel {}

  namespace Meta {}
 
  namespace Meta {

    namespace Sequential {}

    namespace Parallel {}
 
  }
 

  namespace Config {
    const bool clone = true;
    const double threads = 1.0;

    const unsigned int c_d = 8;
    const unsigned int a_d = 2;

    const unsigned int steal_limit = 3;
    const unsigned int initial_delay = 5;

    const unsigned int d_l = 5;

    const double base = 1.5;
    const unsigned int slice = 250;

    const unsigned int nogoods_limit = 128;

    const unsigned int cpprofiler_port = 6565U;
  }
 
}}
 
#include <gecode/search/exception.hpp>
 
namespace Gecode { namespace Search {

  class Statistics : public StatusStatistics {
  public:
    unsigned long long int fail;
    unsigned long long int node;
    unsigned long int depth;
    unsigned long int restart;
    unsigned long int nogood;
    Statistics(void);
    void reset(void);
    Statistics operator +(const Statistics& s);
    Statistics& operator +=(const Statistics& s);
  };
 
}}
 
#include <gecode/search/statistics.hpp>
 
namespace Gecode { namespace Search {
 
  class WrapTraceRecorder;
  class TraceRecorder;
  class EdgeTraceRecorder;
 
}}
 
#include <string>
#include <sstream>
 
namespace Gecode {

  class SearchTracer {
    friend class Search::WrapTraceRecorder;
    friend class Search::TraceRecorder;
    friend class Search::EdgeTraceRecorder;
  public:
    enum EngineType {
      DFS = 0, 
      BAB = 1, 
      LDS = 2, 
      RBS = 3, 
      PBS = 4, 
      AOE = 5  
    };

    class EngineInfo {
    protected:
      EngineType _type;
      unsigned int _fst;
      unsigned int _lst;
    public:
      EngineInfo(void);
      EngineInfo(EngineType et, unsigned int fst, unsigned int lst);


      EngineType type(void) const;
      bool meta(void) const;


      unsigned int wfst(void) const;
      unsigned int wlst(void) const;
      unsigned int workers(void) const;


      unsigned int efst(void) const;
      unsigned int elst(void) const;
      unsigned int engines(void) const;
    };

    class EdgeInfo {
    protected:
      unsigned int _wid;
      unsigned int _nid;
      unsigned int _a;
      std::string _s;
    public:
      void init(unsigned int wid, unsigned int nid, unsigned int a);
      void init(unsigned int wid, unsigned int nid, unsigned int a,
                const Space& s, const Choice & c);
      void invalidate(void);
      EdgeInfo(void);
      EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
      operator bool(void) const;
      unsigned int wid(void) const;
      unsigned int nid(void) const;
      unsigned int alternative(void) const;
      std::string string(void) const;
    };

    enum NodeType {
      SOLVED  = 0, 
      FAILED  = 1, 
      BRANCH  = 2  
    };

    class NodeInfo {
    protected:
      NodeType _nt;
      unsigned int _wid;
      unsigned int _nid;
      const Space& _s;
      const Choice* _c;
    public:
      NodeInfo(NodeType nt,
               unsigned int wid, unsigned int nid,
               const Space& s, const Choice* c = nullptr);
      NodeType type(void) const;
      unsigned int wid(void) const;
      unsigned int nid(void) const;
      const Space& space(void) const;
      const Choice& choice(void) const;
    };
  private:
    Support::Mutex m;
    unsigned int pending;
    unsigned int n_e;
    unsigned int n_w;
    unsigned int n_active;
    Support::DynamicArray<EngineInfo,Heap> es;
    Support::DynamicArray<unsigned int,Heap> w2e;
    void engine(EngineType t, unsigned int n);
    void worker(unsigned int& wid, unsigned int& eid);
    void worker(void);
    //{@
    void _round(unsigned int eid);
    void _skip(const EdgeInfo& ei);
    void _node(const EdgeInfo& ei, const NodeInfo& ni);
  public:
    SearchTracer(void);


    unsigned int workers(void) const;
    unsigned int engines(void) const;
    const EngineInfo& engine(unsigned int eid) const;
    unsigned int eid(unsigned int wid) const;


    virtual void init(void) = 0;
    virtual void round(unsigned int eid) = 0;
    virtual void skip(const EdgeInfo& ei) = 0;
    virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
    virtual void done(void) = 0;

    virtual ~SearchTracer(void);
  };
 
  class GECODE_SEARCH_EXPORT StdSearchTracer : public SearchTracer {
  protected:
    std::ostream& os;
    static const char* t2s[EngineType::AOE + 1];
  public:
    StdSearchTracer(std::ostream& os = std::cerr);
    virtual void init(void);
    virtual void round(unsigned int eid);
    virtual void skip(const EdgeInfo& ei);
    virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
    virtual void done(void);
    virtual ~StdSearchTracer(void);
    static StdSearchTracer def;
  };
 
}
 
#include <gecode/search/tracer.hpp>
#include <gecode/search/trace-recorder.hpp>
 
#ifdef GECODE_HAS_CPPROFILER
 
namespace Gecode {

  namespace CPProfiler {}
 
}
 
namespace Gecode { namespace CPProfiler {

  class Connector;
 
}}
 
namespace Gecode {

  class GECODE_SEARCH_EXPORT CPProfilerSearchTracer : public SearchTracer {
  public:
    class GECODE_SEARCH_EXPORT GetInfo : public HeapAllocated {
    public:
      GetInfo(void);
      virtual std::string getInfo(const Space& home) const = 0;
      virtual ~GetInfo(void);
    };
  private:
    CPProfiler::Connector* connector;
    int execution_id;
    std::string name;
    int restart;
    const GetInfo* pgi;
  public:
    CPProfilerSearchTracer(int eid, std::string name,
                           unsigned int port = Search::Config::cpprofiler_port,
                           const GetInfo* pgi = nullptr);
    virtual void init(void);
    virtual void round(unsigned int eid);
    virtual void skip(const EdgeInfo& ei);
    virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
    virtual void done(void);
    virtual ~CPProfilerSearchTracer(void);
  };
 
}
 
#endif
 
namespace Gecode { namespace Search {

  class GECODE_SEARCH_EXPORT Cutoff : public HeapAllocated {
  public:


    Cutoff(void);
    virtual unsigned long long int operator ()(void) const = 0;
    virtual unsigned long long int operator ++(void) = 0;
    virtual ~Cutoff(void);


    static Cutoff*
    constant(unsigned long long int scale=Config::slice);
    static Cutoff*
    linear(unsigned long long int scale=Config::slice);
    static Cutoff*
    geometric(unsigned long long int scale=Config::slice,
              double base=Config::base);
    static Cutoff*
    luby(unsigned long long int scale=Config::slice);
    static Cutoff*
    rnd(unsigned int seed,
        unsigned long long int min, unsigned long long int max,
        unsigned long long int n);
    static Cutoff*
    append(Cutoff* c1, unsigned long long int n, Cutoff* c2);
    static Cutoff*
    merge(Cutoff* c1, Cutoff* c2);
    static Cutoff*
    repeat(Cutoff* c, unsigned long long int n);
  };

  class GECODE_SEARCH_EXPORT CutoffConstant : public Cutoff {
  protected:
    unsigned long long int c;
  public:
    CutoffConstant(unsigned long long int c);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffLinear : public Cutoff {
  protected:
    unsigned long long int scale;
    unsigned long long int n;
  public:
    CutoffLinear(unsigned long long int scale);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffLuby : public Cutoff {
  protected:
    unsigned long long int i;
    unsigned long long int scale;
    static const unsigned long long int n_start = 63U;
    static unsigned long int start[n_start];
    static unsigned long long int log(unsigned long long int i);
    static unsigned long long int luby(unsigned long long int i);
  public:
    CutoffLuby(unsigned long long int scale);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffGeometric : public Cutoff {
  protected:
    double n;
    double scale;
    double base;
  public:
    CutoffGeometric(unsigned long long int scale, double base);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffRandom : public Cutoff {
  protected:
    Support::RandomGenerator rnd;
    unsigned long long int min;
    unsigned long long int n;
    unsigned long long int step;
    unsigned long long int cur;
  public:
    CutoffRandom(unsigned int seed,
                 unsigned long long int min, unsigned long long int max,
                 unsigned long long int n);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffAppend : public Cutoff {
  protected:
    Cutoff* c1;
    Cutoff* c2;
    unsigned long long int n;
  public:
    CutoffAppend(Cutoff* c1, unsigned long long int n, Cutoff* c2);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
    virtual ~CutoffAppend(void);
  };

  class GECODE_SEARCH_EXPORT CutoffMerge : public Cutoff {
  protected:
    Cutoff* c1;
    Cutoff* c2;
  public:
    CutoffMerge(Cutoff* c1, Cutoff* c2);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
    virtual ~CutoffMerge(void);
  };

  class GECODE_SEARCH_EXPORT CutoffRepeat : public Cutoff {
  protected:
    Cutoff* c;
    // Current cutoff
    unsigned long long int cutoff;
    // Iteration
    unsigned long long int i;
    // Number of repetitions
    unsigned long long int n;
  public:
    CutoffRepeat(Cutoff* c, unsigned long long int n);
    virtual unsigned long long int operator ()(void) const;
    virtual unsigned long long int operator ++(void);
    virtual ~CutoffRepeat(void);
  };
 
}}
 
#include <gecode/search/cutoff.hpp>
 
namespace Gecode { namespace Search {
 
    class Stop;

    class Options {
    public:
      bool clone;
      double threads;
      unsigned int c_d;
      unsigned int a_d;
      unsigned int d_l;
      unsigned int assets;
      unsigned int slice;
      unsigned int nogoods_limit;
      Stop* stop;
      Cutoff* cutoff;
      SearchTracer* tracer;
      GECODE_SEARCH_EXPORT static const Options def;
      Options(void);
      GECODE_SEARCH_EXPORT Options
      expand(void) const;
    };
 
}}
 
#include <gecode/search/options.hpp>
 
namespace Gecode { namespace Search {


  class GECODE_SEARCH_EXPORT Stop : public HeapAllocated {
  public:


    Stop(void);
    virtual bool stop(const Statistics& s, const Options& o) = 0;
    virtual ~Stop(void);


    static Stop* node(unsigned long long int l);
    static Stop* fail(unsigned long long int l);
    static Stop* time(double l);
    static Stop* restart(unsigned long long int l);
  };

  class GECODE_SEARCH_EXPORT NodeStop : public Stop {
  protected:
    std::atomic<unsigned long long int> l;
  public:
    NodeStop(unsigned long long int l);
    NodeStop(const NodeStop& s);
    NodeStop& operator =(const NodeStop& s);
    unsigned long long int limit(void) const;
    void limit(unsigned long long int l);
    virtual bool stop(const Statistics& s, const Options& o);
  };

  class GECODE_SEARCH_EXPORT FailStop : public Stop {
  protected:
    std::atomic<unsigned long long int> l;
  public:
    FailStop(unsigned long long int l);
    FailStop(const FailStop& s);
    FailStop& operator =(const FailStop& s);
    unsigned long long int limit(void) const;
    void limit(unsigned long long int l);
    virtual bool stop(const Statistics& s, const Options& o);
  };

  class GECODE_SEARCH_EXPORT TimeStop : public Stop {
  protected:
    using clock = std::chrono::steady_clock;
    using clock_rep = clock::time_point::rep;
    std::atomic<clock_rep> t0;
    std::atomic<double> l;
  public:
    TimeStop(double l);
    TimeStop(const TimeStop& s);
    TimeStop& operator =(const TimeStop& s);
    double limit(void) const;
    void limit(double l);
    void reset(void);
    virtual bool stop(const Statistics& s, const Options& o);
  };

  class GECODE_SEARCH_EXPORT RestartStop : public Stop {
  protected:
    std::atomic<unsigned long long int> l;
  public:
    RestartStop(unsigned long long int l);
    RestartStop(const RestartStop& s);
    RestartStop& operator =(const RestartStop& s);
    unsigned long long int limit(void) const;
    void limit(unsigned long long int l);
    virtual bool stop(const Statistics& s, const Options& o);
  };
 
}}
 
#include <gecode/search/stop.hpp>
 
namespace Gecode { namespace Search {

  class GECODE_SEARCH_EXPORT Engine : public HeapAllocated {
  public:
    virtual Space* next(void) = 0;
    virtual Statistics statistics(void) const = 0;
    virtual bool stopped(void) const = 0;
    virtual void constrain(const Space& b);
    virtual void reset(Space* s);
    virtual NoGoods& nogoods(void);
    virtual ~Engine(void);
  };
 
}}
 
#include <gecode/search/engine.hpp>
 
namespace Gecode { namespace Search {

  template<class T>
  class Base : public HeapAllocated {
    template<class, class>
    friend Engine* build(Space*, const Options&);
    template<class, template<class> class>
    friend Engine* build(Space*, const Options&);
  protected:
    Engine* e;
    Base(Engine* e = nullptr);
  public:
    virtual T* next(void);
    virtual Statistics statistics(void) const;
    virtual bool stopped(void) const;
    virtual ~Base(void);
  private:
    Base(const Base&);
    Base& operator =(const Base&);
  };
 
}}
 
#include <gecode/search/base.hpp>
 
namespace Gecode { namespace Search {

  template<class T, class E>
  Engine* build(Space* s, const Options& opt);
  template<class T, template<class> class E>
  Engine* build(Space* s, const Options& opt);

  class GECODE_SEARCH_EXPORT Builder : public HeapAllocated {
  protected:
    Options opt;
    const bool b;
  public:
    Builder(const Options& opt, bool best);
    Options& options(void);
    const Options& options(void) const;
    bool best(void) const;
    virtual Engine* operator() (Space* s) const = 0;
    virtual ~Builder(void);
  };
 
}}
 
#include <gecode/search/build.hpp>
 
namespace Gecode {

  typedef Search::Builder* SEB;
 
}
 
#include <gecode/search/traits.hpp>
 
namespace Gecode {

  class SEBs : public ArgArray<SEB> {
  public:


    SEBs(void);
    explicit SEBs(int n);
    SEBs(const std::vector<SEB>& x);
    SEBs(std::initializer_list<SEB> x);
    template<class InputIterator>
    SEBs(InputIterator first, InputIterator last);
    SEBs(const ArgArray<SEB>& a);
  };
 
}
 
#include <gecode/search/sebs.hpp>
 
namespace Gecode {

  template<class T>
  class DFS : public Search::Base<T> {
  public:
    DFS(T* s, const Search::Options& o=Search::Options::def);
    static const bool best = false;
  };

  template<class T>
  T* dfs(T* s, const Search::Options& o=Search::Options::def);

  template<class T>
  SEB dfs(const Search::Options& o=Search::Options::def);
 
}
 
#include <gecode/search/dfs.hpp>
 
namespace Gecode {

  template<class T>
  class BAB : public Search::Base<T> {
  public:
    BAB(T* s, const Search::Options& o=Search::Options::def);
    static const bool best = true;
  };

  template<class T>
  T* bab(T* s, const Search::Options& o=Search::Options::def);

  template<class T>
  SEB bab(const Search::Options& o=Search::Options::def);
 
}
 
#include <gecode/search/bab.hpp>
 
namespace Gecode {

  template<class T>
  class LDS : public Search::Base<T> {
  public:
    LDS(T* s, const Search::Options& o=Search::Options::def);
    static const bool best = false;
  };

  template<class T>
  T* lds(T* s, const Search::Options& o=Search::Options::def);

  template<class T>
  SEB lds(const Search::Options& o=Search::Options::def);
 
}
 
#include <gecode/search/lds.hpp>
 
namespace Gecode {

  template<class T, template<class> class E = DFS>
  class RBS : public Search::Base<T> {
    using Search::Base<T>::e;
  public:
    RBS(T* s, const Search::Options& o);
    static const bool best = E<T>::best;
  };

  template<class T, template<class> class E>
  T* rbs(T* s, const Search::Options& o);

  template<class T, template<class> class E>
  SEB rbs(const Search::Options& o);
 
}
 
#include <gecode/search/rbs.hpp>
 
namespace Gecode { namespace Search { namespace Meta {

  template<class T, template<class> class E>
  Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);

  template<class T, template<class> class E>
  Engine* sequential(T* master, SEBs& sebs,
                     const Search::Statistics& stat, Options& opt, bool best);
 
#ifdef GECODE_HAS_THREADS

  template<class T, template<class> class E>
  Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);

  template<class T, template<class> class E>
  Engine* parallel(T* master, SEBs& sebs,
                   const Search::Statistics& stat, Options& opt, bool best);
 
#endif
 
}}}
 
namespace Gecode {

  template<class T, template<class> class E = DFS>
  class PBS : public Search::Base<T> {
    using Search::Base<T>::e;
  protected:
    void build(T* s, SEBs& sebs, const Search::Options& o);
  public:
    PBS(T* s, const Search::Options& o=Search::Options::def);
    PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
    static const bool best = E<T>::best;
  };

  template<class T, template<class> class E>
  T* pbs(T* s, const Search::Options& o=Search::Options::def);

  template<class T>
  SEB pbs(const Search::Options& o=Search::Options::def);
 
}
 
#include <gecode/search/pbs.hpp>
 
#endif
 
// STATISTICS: search-other