Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
search.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Contributing authors:
8  * Kevin Leo <kevin.leo@monash.edu>
9  * Maxim Shishmarev <maxim.shishmarev@monash.edu>
10  *
11  * Copyright:
12  * Kevin Leo, 2017
13  * Christian Schulte, 2002
14  * Maxim Shishmarev, 2017
15  * Guido Tack, 2004
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #ifndef __GECODE_SEARCH_HH__
43 #define __GECODE_SEARCH_HH__
44 
45 #include <initializer_list>
46 
47 #include <gecode/kernel.hh>
48 
49 /*
50  * Configure linking
51  *
52  */
53 #if !defined(GECODE_STATIC_LIBS) && \
54  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
55 
56 #ifdef GECODE_BUILD_SEARCH
57 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
58 #else
59 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
60 #endif
61 
62 #else
63 
64 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
65 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
66 #else
67 #define GECODE_SEARCH_EXPORT
68 #endif
69 
70 #endif
71 
72 // Configure auto-linking
73 #ifndef GECODE_BUILD_SEARCH
74 #define GECODE_LIBRARY_NAME "Search"
76 #endif
77 
78 
79 namespace Gecode { namespace Search {
80 
82  namespace Sequential {}
83 
85  namespace Parallel {}
86 
88  namespace Meta {}
89 
90  namespace Meta {
91 
93  namespace Sequential {}
94 
96  namespace Parallel {}
97 
98  }
99 
100 
106  namespace Config {
108  const bool clone = true;
110  const double threads = 1.0;
111 
113  const unsigned int c_d = 8;
115  const unsigned int a_d = 2;
116 
118  const unsigned int steal_limit = 3;
120  const unsigned int initial_delay = 5;
121 
123  const unsigned int d_l = 5;
124 
126  const double base = 1.5;
128  const unsigned int slice = 250;
129 
131  const unsigned int nogoods_limit = 128;
132 
134  const unsigned int cpprofiler_port = 6565U;
135  }
136 
137 }}
138 
140 
141 namespace Gecode { namespace Search {
142 
147  class Statistics : public StatusStatistics {
148  public:
150  unsigned long int fail;
152  unsigned long int node;
154  unsigned long int depth;
156  unsigned long int restart;
158  unsigned long int nogood;
160  Statistics(void);
162  void reset(void);
164  Statistics operator +(const Statistics& s);
166  Statistics& operator +=(const Statistics& s);
167  };
168 
169 }}
170 
172 
173 namespace Gecode { namespace Search {
174 
175  class WrapTraceRecorder;
176  class TraceRecorder;
177  class EdgeTraceRecorder;
178 
179 }}
180 
181 #include <string>
182 #include <sstream>
183 
184 namespace Gecode {
185 
187  class SearchTracer {
189  friend class Search::TraceRecorder;
191  public:
193  enum EngineType {
194  DFS = 0,
195  BAB = 1,
196  LDS = 2,
197  RBS = 3,
198  PBS = 4,
199  AOE = 5
200  };
202  class EngineInfo {
203  protected:
207  unsigned int _fst;
209  unsigned int _lst;
210  public:
212  EngineInfo(void);
214  EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
216 
217  EngineType type(void) const;
220  bool meta(void) const;
222 
224  unsigned int wfst(void) const;
227  unsigned int wlst(void) const;
229  unsigned int workers(void) const;
231 
233  unsigned int efst(void) const;
236  unsigned int elst(void) const;
238  unsigned int engines(void) const;
240  };
242  class EdgeInfo {
243  protected:
245  unsigned int _wid;
247  unsigned int _nid;
249  unsigned int _a;
251  std::string _s;
252  public:
254  void init(unsigned int wid, unsigned int nid, unsigned int a);
256  void init(unsigned int wid, unsigned int nid, unsigned int a,
257  const Space& s, const Choice & c);
259  void invalidate(void);
261  EdgeInfo(void);
263  EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
265  operator bool(void) const;
267  unsigned int wid(void) const;
269  unsigned int nid(void) const;
271  unsigned int alternative(void) const;
273  std::string string(void) const;
274  };
276  enum NodeType {
277  SOLVED = 0,
278  FAILED = 1,
279  BRANCH = 2
280  };
282  class NodeInfo {
283  protected:
287  unsigned int _wid;
289  unsigned int _nid;
291  const Space& _s;
293  const Choice* _c;
294  public:
296  NodeInfo(NodeType nt,
297  unsigned int wid, unsigned int nid,
298  const Space& s, const Choice* c = nullptr);
300  NodeType type(void) const;
302  unsigned int wid(void) const;
304  unsigned int nid(void) const;
306  const Space& space(void) const;
308  const Choice& choice(void) const;
309  };
310  private:
312  Support::Mutex m;
314  unsigned int pending;
316  unsigned int n_e;
318  unsigned int n_w;
320  unsigned int n_active;
326  void engine(EngineType t, unsigned int n);
328  void worker(unsigned int& wid, unsigned int& eid);
330  void worker(void);
332  //{@
334  void _round(unsigned int eid);
336  void _skip(const EdgeInfo& ei);
338  void _node(const EdgeInfo& ei, const NodeInfo& ni);
340  public:
342  SearchTracer(void);
344 
345  unsigned int workers(void) const;
348  unsigned int engines(void) const;
350  const EngineInfo& engine(unsigned int eid) const;
352  unsigned int eid(unsigned int wid) const;
354 
356  virtual void init(void) = 0;
359  virtual void round(unsigned int eid) = 0;
361  virtual void skip(const EdgeInfo& ei) = 0;
363  virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
365  virtual void done(void) = 0;
367  virtual ~SearchTracer(void);
369  };
370 
372  protected:
374  std::ostream& os;
376  static const char* t2s[EngineType::AOE + 1];
377  public:
379  StdSearchTracer(std::ostream& os = std::cerr);
381  virtual void init(void);
383  virtual void round(unsigned int eid);
385  virtual void skip(const EdgeInfo& ei);
387  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
389  virtual void done(void);
391  virtual ~StdSearchTracer(void);
394  };
395 
396 }
397 
398 #include <gecode/search/tracer.hpp>
400 
401 #ifdef GECODE_HAS_CPPROFILER
402 
403 namespace Gecode {
404 
406  namespace CPProfiler {}
407 
408 }
409 
410 namespace Gecode { namespace CPProfiler {
411 
413  class Connector;
414 
415 }}
416 
417 namespace Gecode {
418 
421  public:
424  public:
426  GetInfo(void);
428  virtual std::string getInfo(const Space& home) const = 0;
430  virtual ~GetInfo(void);
431  };
432  private:
434  CPProfiler::Connector* connector;
436  int execution_id;
438  std::string name;
440  int restart;
442  const GetInfo* pgi;
443  public:
445  CPProfilerSearchTracer(int eid, std::string name,
446  unsigned int port = Search::Config::cpprofiler_port,
447  const GetInfo* pgi = nullptr);
449  virtual void init(void);
451  virtual void round(unsigned int eid);
453  virtual void skip(const EdgeInfo& ei);
455  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
457  virtual void done(void);
459  virtual ~CPProfilerSearchTracer(void);
460  };
461 
462 }
463 
464 #endif
465 
466 namespace Gecode { namespace Search {
467 
473  public:
475 
476  Cutoff(void);
479  virtual unsigned long int operator ()(void) const = 0;
481  virtual unsigned long int operator ++(void) = 0;
483  virtual ~Cutoff(void);
485 
487  static Cutoff*
489  constant(unsigned long int scale=Config::slice);
491  static Cutoff*
492  linear(unsigned long int scale=Config::slice);
496  static Cutoff*
497  geometric(unsigned long int scale=Config::slice, double base=Config::base);
499  static Cutoff*
500  luby(unsigned long int scale=Config::slice);
505  static Cutoff*
506  rnd(unsigned int seed,
507  unsigned long int min, unsigned long int max,
508  unsigned long int n);
510  static Cutoff*
511  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
513  static Cutoff*
514  merge(Cutoff* c1, Cutoff* c2);
516  static Cutoff*
517  repeat(Cutoff* c, unsigned long int n);
519  };
520 
526  protected:
528  unsigned long int c;
529  public:
531  CutoffConstant(unsigned long int c);
533  virtual unsigned long int operator ()(void) const;
535  virtual unsigned long int operator ++(void);
536  };
537 
543  protected:
545  unsigned long int scale;
547  unsigned long int n;
548  public:
550  CutoffLinear(unsigned long int scale);
552  virtual unsigned long int operator ()(void) const;
554  virtual unsigned long int operator ++(void);
555  };
556 
562  protected:
564  unsigned long int i;
566  unsigned long int scale;
568  static const unsigned long int n_start = 63U;
570  static unsigned long int start[n_start];
572  static unsigned long int log(unsigned long int i);
574  static unsigned long int luby(unsigned long int i);
575  public:
577  CutoffLuby(unsigned long int scale);
579  virtual unsigned long int operator ()(void) const;
581  virtual unsigned long int operator ++(void);
582  };
583 
589  protected:
591  double n;
593  double scale;
595  double base;
596  public:
598  CutoffGeometric(unsigned long int scale, double base);
600  virtual unsigned long int operator ()(void) const;
602  virtual unsigned long int operator ++(void);
603  };
604 
610  protected:
614  unsigned long int min;
616  unsigned long int n;
618  unsigned long int step;
620  unsigned long int cur;
621  public:
623  CutoffRandom(unsigned int seed,
624  unsigned long int min, unsigned long int max,
625  unsigned long int n);
627  virtual unsigned long int operator ()(void) const;
629  virtual unsigned long int operator ++(void);
630  };
631 
637  protected:
643  unsigned long int n;
644  public:
646  CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
648  virtual unsigned long int operator ()(void) const;
650  virtual unsigned long int operator ++(void);
652  virtual ~CutoffAppend(void);
653  };
654 
660  protected:
665  public:
667  CutoffMerge(Cutoff* c1, Cutoff* c2);
669  virtual unsigned long int operator ()(void) const;
671  virtual unsigned long int operator ++(void);
673  virtual ~CutoffMerge(void);
674  };
675 
681  protected:
684  // Current cutoff
685  unsigned int cutoff;
686  // Iteration
687  unsigned long int i;
688  // Number of repetitions
689  unsigned long int n;
690  public:
692  CutoffRepeat(Cutoff* c, unsigned long int n);
694  virtual unsigned long int operator ()(void) const;
696  virtual unsigned long int operator ++(void);
698  virtual ~CutoffRepeat(void);
699  };
700 
701 }}
702 
703 #include <gecode/search/cutoff.hpp>
704 
705 namespace Gecode { namespace Search {
706 
707  class Stop;
708 
746  class Options {
747  public:
749  bool clone;
751  double threads;
753  unsigned int c_d;
755  unsigned int a_d;
757  unsigned int d_l;
759  unsigned int assets;
761  unsigned int slice;
763  unsigned int nogoods_limit;
773  Options(void);
776  expand(void) const;
777  };
778 
779 }}
780 
781 #include <gecode/search/options.hpp>
782 
783 namespace Gecode { namespace Search {
784 
800  public:
802 
803  Stop(void);
806  virtual bool stop(const Statistics& s, const Options& o) = 0;
808  virtual ~Stop(void);
810 
812  static Stop* node(unsigned long int l);
815  static Stop* fail(unsigned long int l);
817  static Stop* time(unsigned long int l);
819  };
820 
830  protected:
832  unsigned long int l;
833  public:
835  NodeStop(unsigned long int l);
837  unsigned long int limit(void) const;
839  void limit(unsigned long int l);
841  virtual bool stop(const Statistics& s, const Options& o);
842  };
843 
853  protected:
855  unsigned long int l;
856  public:
858  FailStop(unsigned long int l);
860  unsigned long int limit(void) const;
862  void limit(unsigned long int l);
864  virtual bool stop(const Statistics& s, const Options& o);
865  };
866 
872  protected:
876  unsigned long int l;
877  public:
879  TimeStop(unsigned long int l);
881  unsigned long int limit(void) const;
883  void limit(unsigned long int l);
885  void reset(void);
887  virtual bool stop(const Statistics& s, const Options& o);
888  };
889 
890 }}
891 
892 #include <gecode/search/stop.hpp>
893 
894 namespace Gecode { namespace Search {
895 
900  public:
902  virtual Space* next(void) = 0;
904  virtual Statistics statistics(void) const = 0;
906  virtual bool stopped(void) const = 0;
908  virtual void constrain(const Space& b);
910  virtual void reset(Space* s);
912  virtual NoGoods& nogoods(void);
914  virtual ~Engine(void);
915  };
916 
917 }}
918 
919 #include <gecode/search/engine.hpp>
920 
921 namespace Gecode { namespace Search {
922 
924  template<class T>
925  class Base : public HeapAllocated {
926  template<class, class>
927  friend Engine* build(Space*, const Options&);
928  template<class, template<class> class>
929  friend Engine* build(Space*, const Options&);
930  protected:
934  Base(Engine* e = NULL);
935  public:
937  virtual T* next(void);
939  virtual Statistics statistics(void) const;
941  virtual bool stopped(void) const;
943  virtual ~Base(void);
944  private:
946  Base(const Base&);
948  Base& operator =(const Base&);
949  };
950 
951 }}
952 
953 #include <gecode/search/base.hpp>
954 
955 namespace Gecode { namespace Search {
956 
958  template<class T, class E>
959  Engine* build(Space* s, const Options& opt);
961  template<class T, template<class> class E>
962  Engine* build(Space* s, const Options& opt);
963 
966  protected:
970  const bool b;
971  public:
973  Builder(const Options& opt, bool best);
975  Options& options(void);
977  const Options& options(void) const;
979  bool best(void) const;
981  virtual Engine* operator() (Space* s) const = 0;
983  virtual ~Builder(void);
984  };
985 
986 }}
987 
988 #include <gecode/search/build.hpp>
989 
990 namespace Gecode {
991 
994 
995 }
996 
997 #include <gecode/search/traits.hpp>
998 
999 namespace Gecode {
1000 
1002  class SEBs : public ArgArray<SEB> {
1003  public:
1005 
1006  SEBs(void);
1009  explicit SEBs(int n);
1011  SEBs(const std::vector<SEB>& x);
1013  SEBs(std::initializer_list<SEB> x);
1015  template<class InputIterator>
1016  SEBs(InputIterator first, InputIterator last);
1018  SEBs(const ArgArray<SEB>& a);
1020  };
1021 
1022 }
1023 
1024 #include <gecode/search/sebs.hpp>
1025 
1026 namespace Gecode {
1027 
1035  template<class T>
1036  class DFS : public Search::Base<T> {
1037  public:
1039  DFS(T* s, const Search::Options& o=Search::Options::def);
1041  static const bool best = false;
1042  };
1043 
1045  template<class T>
1046  T* dfs(T* s, const Search::Options& o=Search::Options::def);
1047 
1049  template<class T>
1051 
1052 }
1053 
1054 #include <gecode/search/dfs.hpp>
1055 
1056 namespace Gecode {
1057 
1069  template<class T>
1070  class BAB : public Search::Base<T> {
1071  public:
1073  BAB(T* s, const Search::Options& o=Search::Options::def);
1075  static const bool best = true;
1076  };
1077 
1090  template<class T>
1091  T* bab(T* s, const Search::Options& o=Search::Options::def);
1092 
1094  template<class T>
1096 
1097 }
1098 
1099 #include <gecode/search/bab.hpp>
1100 
1101 namespace Gecode {
1102 
1107  template<class T>
1108  class LDS : public Search::Base<T> {
1109  public:
1111  LDS(T* s, const Search::Options& o=Search::Options::def);
1113  static const bool best = false;
1114  };
1115 
1120  template<class T>
1121  T* lds(T* s, const Search::Options& o=Search::Options::def);
1122 
1124  template<class T>
1126 
1127 }
1128 
1129 #include <gecode/search/lds.hpp>
1130 
1131 namespace Gecode {
1132 
1151  template<class T, template<class> class E = DFS>
1152  class RBS : public Search::Base<T> {
1153  using Search::Base<T>::e;
1154  public:
1156  RBS(T* s, const Search::Options& o);
1158  static const bool best = E<T>::best;
1159  };
1160 
1179  template<class T, template<class> class E>
1180  T* rbs(T* s, const Search::Options& o);
1181 
1183  template<class T, template<class> class E>
1184  SEB rbs(const Search::Options& o);
1185 
1186 }
1187 
1188 #include <gecode/search/rbs.hpp>
1189 
1190 namespace Gecode { namespace Search { namespace Meta {
1191 
1193  template<class T, template<class> class E>
1194  Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
1195 
1197  template<class T, template<class> class E>
1198  Engine* sequential(T* master, SEBs& sebs,
1199  const Search::Statistics& stat, Options& opt, bool best);
1200 
1201 #ifdef GECODE_HAS_THREADS
1202 
1204  template<class T, template<class> class E>
1205  Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
1206 
1208  template<class T, template<class> class E>
1209  Engine* parallel(T* master, SEBs& sebs,
1210  const Search::Statistics& stat, Options& opt, bool best);
1211 
1212 #endif
1213 
1214 }}}
1215 
1216 namespace Gecode {
1217 
1235  template<class T, template<class> class E = DFS>
1236  class PBS : public Search::Base<T> {
1237  using Search::Base<T>::e;
1238  protected:
1240  void build(T* s, SEBs& sebs, const Search::Options& o);
1241  public:
1243  PBS(T* s, const Search::Options& o=Search::Options::def);
1245  PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
1247  static const bool best = E<T>::best;
1248  };
1249 
1267  template<class T, template<class> class E>
1268  T* pbs(T* s, const Search::Options& o=Search::Options::def);
1269 
1271  template<class T>
1273 
1274 }
1275 
1276 #include <gecode/search/pbs.hpp>
1277 
1278 #endif
1279 
1280 // STATISTICS: search-other
Timer
Definition: timer.hpp:51
SearchTracer(void)
Initialize.
Definition: tracer.hpp:220
Post propagator for SetVar x
Definition: set.hh:767
Base(Engine *e=NULL)
Constructor.
Definition: base.hpp:42
const unsigned int cpprofiler_port
Default port for CPProfiler.
Definition: search.hh:134
unsigned long int n
Next number in sequence.
Definition: search.hh:547
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
Cutoff generator for linear sequence.
Definition: search.hh:542
unsigned int wlst(void) const
Return id of last worker plus one.
Definition: tracer.hpp:68
unsigned long int l
Node limit.
Definition: search.hh:832
Support::Timer t
Time when execution should stop.
Definition: search.hh:874
#define GECODE_SEARCH_EXPORT
Definition: search.hh:67
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
unsigned long int i
Iteration number.
Definition: search.hh:564
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Search engine options
Definition: search.hh:746
unsigned int _wid
The worker id.
Definition: search.hh:287
A class for building search engines.
Definition: search.hh:965
unsigned int _fst
First worker or engine.
Definition: search.hh:207
Depth-first branch-and-bound search engine.
Definition: search.hh:1070
Options(void)
Initialize with default values.
Definition: options.hpp:37
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition: lds.hpp:69
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
Definition: dfs.hpp:73
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Base-class for Stop-object.
Definition: search.hh:799
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Definition: search.hh:245
static StdSearchTracer def
Default tracer (printing to std::cerr)
Definition: search.hh:393
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition: build.hpp:58
@ AOE
Unspecified engine (any other engine)
Definition: search.hh:199
Limited discrepancy search engine.
Definition: search.hh:1108
NodeType type(void) const
Return node type.
Definition: tracer.hpp:171
@ FAILED
A solution node.
Definition: search.hh:278
NodeType
Node type.
Definition: search.hh:276
double scale
Scale factor.
Definition: search.hh:593
Array with arbitrary number of elements.
@ BRANCH
A failed node.
Definition: search.hh:279
unsigned int nid(void) const
Return parent node id.
Definition: tracer.hpp:142
NodeType t
Type of node.
Definition: bool-expr.cpp:230
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS)
virtual void init(void)=0
The search engine initializes.
const double threads
Number of threads to use.
Definition: search.hh:110
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:680
Computation spaces.
Definition: core.hpp:1742
static const bool best
Whether engine does best solution search.
Definition: search.hh:1041
unsigned int cutoff
Definition: search.hh:685
void invalidate(void)
Invalidate edge information (for stealing)
Definition: tracer.hpp:102
const Space & space(void) const
Return corresponding space.
Definition: tracer.hpp:186
Depth-first search engine.
Definition: search.hh:1036
Base-class for search engines.
Definition: search.hh:925
Statistics operator+(const Statistics &s)
Return sum with s.
Definition: statistics.hpp:61
unsigned long int n
Definition: search.hh:689
virtual bool stop(const Statistics &s, const Options &o)=0
Stop search, if returns true.
Simple recorder for a search tracer.
EngineType _type
The engine type.
Definition: search.hh:205
Recorder for a search tracer with edge information.
virtual void done(void)=0
All workers are done.
SEBs(void)
Allocate empty array.
Definition: sebs.hpp:37
unsigned int _a
Number of alternative.
Definition: search.hh:249
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:154
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
Definition: dfs.hpp:68
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:108
unsigned long int l
Current limit in milliseconds.
Definition: search.hh:876
Stop-object based on time
Definition: search.hh:871
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition: tracer.hpp:165
EngineType type(void) const
Return engine type.
Definition: tracer.hpp:51
unsigned int engines(void) const
Return number of engines.
Definition: tracer.hpp:92
unsigned int workers(void) const
Return number of workers.
Definition: tracer.hpp:261
unsigned int alternative(void) const
Return number of alternative.
Definition: tracer.hpp:148
unsigned int wid(void) const
Return worker id.
Definition: tracer.hpp:176
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:309
Gecode toplevel namespace
unsigned int _lst
Last worker or engine.
Definition: search.hh:209
Search::Builder * SEB
Type for a search engine builder.
Definition: search.hh:993
unsigned long int node
Number of nodes expanded.
Definition: search.hh:152
Passing search engine builder arguments.
Definition: search.hh:1002
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
Definition: statistics.hpp:50
T * bab(T *s, const Search::Options &o)
Perform depth-first branch-and-bound search for subclass T of space s and options o.
Definition: bab.hpp:77
const Space & _s
The corresponding space.
Definition: search.hh:291
No-goods recorded from restarts.
Definition: core.hpp:1588
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:755
unsigned int _nid
The parent node id.
Definition: search.hh:247
Cutoff * c2
Second cutoff generator.
Definition: search.hh:664
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition: pbs.hpp:221
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:767
double base
Base.
Definition: search.hh:595
virtual std::string getInfo(const Space &home) const =0
Return info for a space.
Meta-engine performing restart-based search.
Definition: search.hh:1152
Options opt
The options.
Definition: test.cpp:97
Meta engine using a portfolio of search engines.
Definition: search.hh:1236
Argument array for non-primitive types.
Definition: array.hpp:656
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
Stop * stop
Stop object for stopping search.
Definition: search.hh:765
const unsigned int d_l
Default discrepancy limit for LDS.
Definition: search.hh:123
unsigned long int step
Step size.
Definition: search.hh:618
const Choice & choice(void) const
Return corresponding choice.
Definition: tracer.hpp:191
@ SOLVED
Definition: search.hh:277
Engine * sequential(T *master, const Search::Statistics &stat, Options &opt)
Build a sequential engine.
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:763
EdgeInfo(void)
Initialize as non existing.
Definition: tracer.hpp:127
Node information.
Definition: search.hh:282
Recorder for engine events (for access control)
unsigned long int n
How many number to take from the first.
Definition: search.hh:643
Search engine implementation interface
Definition: search.hh:899
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:131
unsigned long int l
Failure limit.
Definition: search.hh:855
Definition: search.hh:371
Stop-object based on number of nodes
Definition: search.hh:829
Cutoff * c1
First cutoff generator.
Definition: search.hh:662
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:120
unsigned long int n
Random values.
Definition: search.hh:616
double n
Current cutoff value.
Definition: search.hh:591
unsigned long int scale
Scale factor.
Definition: search.hh:566
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition: pbs.hpp:262
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
unsigned long int c
Constant.
Definition: search.hh:528
Template for linear congruential generators.
Definition: random.hpp:46
std::string string(void) const
Return string for alternative.
Definition: tracer.hpp:154
const double base
Base for geometric restart sequence.
Definition: search.hh:126
unsigned long int cur
Current value.
Definition: search.hh:620
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:118
unsigned int _nid
The node id.
Definition: search.hh:289
unsigned int efst(void) const
Return id of first engine.
Definition: tracer.hpp:80
unsigned int wid(void) const
Return parent worker id.
Definition: tracer.hpp:136
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition: search.hh:761
Cutoff generator appending two cutoff generators.
Definition: search.hh:636
Cutoff * c1
First cutoff generators.
Definition: search.hh:639
Base class for heap allocated objects.
Definition: heap.hpp:340
virtual Statistics statistics(void) const =0
Return statistics.
Engine * parallel(T *master, const Search::Statistics &stat, Options &opt)
Build a parallel engine.
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: base.hpp:56
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Cutoff generator for the Luby sequence.
Definition: search.hh:561
virtual bool stopped(void) const =0
Check whether engine has been stopped.
NodeType _nt
The node type.
Definition: search.hh:285
unsigned long int nogood
Number of no-goods posted.
Definition: search.hh:158
static const bool best
Whether engine does best solution search.
Definition: search.hh:1158
static const bool best
Whether engine does best solution search.
Definition: search.hh:1113
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Definition: search.hh:293
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
Edge information.
Definition: search.hh:242
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:472
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:612
Options expand(void) const
Expand with real number of threads.
Definition: options.cpp:43
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Cutoff generator merging two cutoff generators.
Definition: search.hh:659
Class to record search trace info for CPProfiler.
Definition: search.hh:420
Cutoff generator for the geometric sequence.
Definition: search.hh:588
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:107
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition: tracer.hpp:278
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:759
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Definition: build.hpp:58
Statistics for execution of status
Definition: core.hpp:1691
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition: bab.hpp:72
unsigned int nid(void) const
Return node id.
Definition: tracer.hpp:181
std::ostream & os
Output stream to use.
Definition: search.hh:374
virtual Statistics statistics(void) const
Return statistics.
Definition: base.hpp:51
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition: rbs.hpp:83
Definition: connector.hpp:100
Cutoff generator for constant sequence.
Definition: search.hh:525
unsigned int elst(void) const
Return id of last engine.
Definition: tracer.hpp:86
static const bool best
Whether engine does best solution search.
Definition: search.hh:1247
Support for tracing search.
Definition: search.hh:187
std::string _s
String corresponding to alternative.
Definition: search.hh:251
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
EngineInfo(void)
Do not initialize.
Definition: tracer.hpp:43
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
virtual ~Base(void)
Destructor.
Definition: base.hpp:61
Stop-object based on number of failures
Definition: search.hh:852
Options opt
Stored and already expanded options.
Definition: search.hh:968
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
unsigned long int restart
Number of restarts.
Definition: search.hh:156
static const Options def
Default options.
Definition: search.hh:771
Gecode::FloatVal c(-8, 8)
void reset(void)
Reset.
Definition: statistics.hpp:39
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
Definition: search.hh:128
unsigned long int i
Definition: search.hh:687
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Information about an engine.
Definition: search.hh:202
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Choice for performing commit
Definition: core.hpp:1412
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:749
Cutoff * c
Actual cutoff generator.
Definition: search.hh:683
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:757
unsigned int workers(void) const
Return number of workers.
Definition: tracer.hpp:75
Engine * e
The actual search engine.
Definition: search.hh:932
Cutoff * c2
Second cutoff generators.
Definition: search.hh:641
Gecode::IntArgs i({1, 2, 3, 4})
unsigned long int scale
Scale factor.
Definition: search.hh:545
EngineType
Which type of engine.
Definition: search.hh:193
unsigned int engines(void) const
Return number of engines.
Definition: tracer.hpp:266
Search engine statistics
Definition: search.hh:147
static const bool best
Whether engine does best solution search.
Definition: search.hh:1075
Cutoff generator for the random sequence.
Definition: search.hh:609
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Definition: lds.hpp:74
Statistics(void)
Initialize.
Definition: statistics.hpp:45
double threads
Number of threads to use.
Definition: search.hh:751
bool meta(void) const
Return whether engine is a meta engine.
Definition: tracer.hpp:56
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:769
Class to send solution information to CPProfiler.
Definition: search.hh:423
virtual ~SearchTracer(void)
Delete.
Definition: tracer.hpp:284
const bool b
Whether engine to be built is a best solution search engine.
Definition: search.hh:970
unsigned int wfst(void) const
Return id of first worker.
Definition: tracer.hpp:61
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:111
unsigned long int min
Minimum cutoff value.
Definition: search.hh:614