Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
18  * $Date$ by $Author$
19  * $Revision$
20  *
21  * This file is part of Gecode, the generic constraint
22  * development environment:
23  * http://www.gecode.org
24  *
25  * Permission is hereby granted, free of charge, to any person obtaining
26  * a copy of this software and associated documentation files (the
27  * "Software"), to deal in the Software without restriction, including
28  * without limitation the rights to use, copy, modify, merge, publish,
29  * distribute, sublicense, and/or sell copies of the Software, and to
30  * permit persons to whom the Software is furnished to do so, subject to
31  * the following conditions:
32  *
33  * The above copyright notice and this permission notice shall be
34  * included in all copies or substantial portions of the Software.
35  *
36  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
37  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
38  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
39  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
40  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
41  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
42  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
43  *
44  */
45 
46 #ifndef __GECODE_SEARCH_HH__
47 #define __GECODE_SEARCH_HH__
48 
49 #include <gecode/kernel.hh>
50 
51 /*
52  * Configure linking
53  *
54  */
55 #if !defined(GECODE_STATIC_LIBS) && \
56  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
57 
58 #ifdef GECODE_BUILD_SEARCH
59 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
60 #else
61 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
62 #endif
63 
64 #else
65 
66 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
67 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
68 #else
69 #define GECODE_SEARCH_EXPORT
70 #endif
71 
72 #endif
73 
74 // Configure auto-linking
75 #ifndef GECODE_BUILD_SEARCH
76 #define GECODE_LIBRARY_NAME "Search"
78 #endif
79 
80 
81 namespace Gecode { namespace Search {
82 
84  namespace Sequential {}
85 
87  namespace Parallel {}
88 
90  namespace Meta {}
91 
92  namespace Meta {
93 
95  namespace Sequential {}
96 
98  namespace Parallel {}
99 
100  }
101 
102 
108  namespace Config {
110  const bool clone = true;
112  const double threads = 1.0;
113 
115  const unsigned int c_d = 8;
117  const unsigned int a_d = 2;
118 
120  const unsigned int steal_limit = 3;
122  const unsigned int initial_delay = 5;
123 
125  const unsigned int d_l = 5;
126 
128  const double base = 1.5;
130  const unsigned int slice = 250;
131 
133  const unsigned int nogoods_limit = 128;
134 
136  const unsigned int cpprofiler_port = 6565U;
137  }
138 
139 }}
140 
142 
143 namespace Gecode { namespace Search {
144 
149  class Statistics : public StatusStatistics {
150  public:
152  unsigned long int fail;
154  unsigned long int node;
156  unsigned long int depth;
158  unsigned long int restart;
160  unsigned long int nogood;
162  Statistics(void);
164  void reset(void);
166  Statistics operator +(const Statistics& s);
168  Statistics& operator +=(const Statistics& s);
169  };
170 
171 }}
172 
174 
175 namespace Gecode { namespace Search {
176 
177  class WrapTraceRecorder;
178  class TraceRecorder;
179  class EdgeTraceRecorder;
180 
181 }}
182 
183 #include <string>
184 #include <sstream>
185 
186 namespace Gecode {
187 
189  class SearchTracer {
191  friend class Search::TraceRecorder;
193  public:
195  enum EngineType {
196  DFS = 0,
197  BAB = 1,
198  LDS = 2,
199  RBS = 3,
200  PBS = 4,
201  AOE = 5
202  };
204  class EngineInfo {
205  protected:
209  unsigned int _fst;
211  unsigned int _lst;
212  public:
214  EngineInfo(void);
216  EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
218 
219  EngineType type(void) const;
222  bool meta(void) const;
224 
226  unsigned int wfst(void) const;
229  unsigned int wlst(void) const;
231  unsigned int workers(void) const;
233 
235  unsigned int efst(void) const;
238  unsigned int elst(void) const;
240  unsigned int engines(void) const;
242  };
244  class EdgeInfo {
245  protected:
247  unsigned int _wid;
249  unsigned int _nid;
251  unsigned int _a;
253  std::string _s;
254  public:
256  void init(unsigned int wid, unsigned int nid, unsigned int a);
258  void init(unsigned int wid, unsigned int nid, unsigned int a,
259  const Space& s, const Choice & c);
261  void invalidate(void);
263  EdgeInfo(void);
265  EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
267  operator bool(void) const;
269  unsigned int wid(void) const;
271  unsigned int nid(void) const;
273  unsigned int alternative(void) const;
275  std::string string(void) const;
276  };
278  enum NodeType {
279  SOLVED = 0,
280  FAILED = 1,
281  BRANCH = 2
282  };
284  class NodeInfo {
285  protected:
289  unsigned int _wid;
291  unsigned int _nid;
293  const Space& _s;
295  const Choice* _c;
296  public:
298  NodeInfo(NodeType nt,
299  unsigned int wid, unsigned int nid,
300  const Space& s, const Choice* c = nullptr);
302  NodeType type(void) const;
304  unsigned int wid(void) const;
306  unsigned int nid(void) const;
308  const Space& space(void) const;
310  const Choice& choice(void) const;
311  };
312  private:
314  Support::Mutex m;
316  unsigned int pending;
318  unsigned int n_e;
320  unsigned int n_w;
322  unsigned int n_active;
328  void engine(EngineType t, unsigned int n);
330  void worker(unsigned int& wid, unsigned int& eid);
332  void worker(void);
334  //{@
336  void _round(unsigned int eid);
338  void _skip(const EdgeInfo& ei);
340  void _node(const EdgeInfo& ei, const NodeInfo& ni);
342  public:
344  SearchTracer(void);
346 
347  unsigned int workers(void) const;
350  unsigned int engines(void) const;
352  const EngineInfo& engine(unsigned int eid) const;
354  unsigned int eid(unsigned int wid) const;
356 
358  virtual void init(void) = 0;
361  virtual void round(unsigned int eid) = 0;
363  virtual void skip(const EdgeInfo& ei) = 0;
365  virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
367  virtual void done(void) = 0;
369  virtual ~SearchTracer(void);
371  };
372 
374  protected:
376  std::ostream& os;
378  static const char* t2s[EngineType::AOE + 1];
379  public:
381  StdSearchTracer(std::ostream& os = std::cerr);
383  virtual void init(void);
385  virtual void round(unsigned int eid);
387  virtual void skip(const EdgeInfo& ei);
389  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
391  virtual void done(void);
393  virtual ~StdSearchTracer(void);
396  };
397 
398 }
399 
400 #include <gecode/search/tracer.hpp>
402 
403 #ifdef GECODE_HAS_CPPROFILER
404 
405 namespace Gecode {
406 
408  namespace CPProfiler {}
409 
410 }
411 
412 namespace Gecode { namespace CPProfiler {
413 
415  class Connector;
416 
417 }}
418 
419 namespace Gecode {
420 
423  public:
426  public:
428  GetInfo(void);
430  virtual std::string getInfo(const Space& home) const = 0;
432  virtual ~GetInfo(void);
433  };
434  private:
436  CPProfiler::Connector* connector;
438  int execution_id;
440  std::string name;
442  int restart;
444  const GetInfo* pgi;
445  public:
447  CPProfilerSearchTracer(int eid, std::string name,
448  unsigned int port = Search::Config::cpprofiler_port,
449  const GetInfo* pgi = nullptr);
451  virtual void init(void);
453  virtual void round(unsigned int eid);
455  virtual void skip(const EdgeInfo& ei);
457  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
459  virtual void done(void);
461  virtual ~CPProfilerSearchTracer(void);
462  };
463 
464 }
465 
466 #endif
467 
468 namespace Gecode { namespace Search {
469 
475  public:
477 
478  Cutoff(void);
481  virtual unsigned long int operator ()(void) const = 0;
483  virtual unsigned long int operator ++(void) = 0;
485  virtual ~Cutoff(void);
487 
489  static Cutoff*
491  constant(unsigned long int scale=Config::slice);
493  static Cutoff*
494  linear(unsigned long int scale=Config::slice);
498  static Cutoff*
499  geometric(unsigned long int scale=Config::slice, double base=Config::base);
501  static Cutoff*
502  luby(unsigned long int scale=Config::slice);
507  static Cutoff*
508  rnd(unsigned int seed,
509  unsigned long int min, unsigned long int max,
510  unsigned long int n);
512  static Cutoff*
513  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
515  static Cutoff*
516  merge(Cutoff* c1, Cutoff* c2);
518  static Cutoff*
519  repeat(Cutoff* c, unsigned long int n);
521  };
522 
528  protected:
530  unsigned long int c;
531  public:
533  CutoffConstant(unsigned long int c);
535  virtual unsigned long int operator ()(void) const;
537  virtual unsigned long int operator ++(void);
538  };
539 
545  protected:
547  unsigned long int scale;
549  unsigned long int n;
550  public:
552  CutoffLinear(unsigned long int scale);
554  virtual unsigned long int operator ()(void) const;
556  virtual unsigned long int operator ++(void);
557  };
558 
564  protected:
566  unsigned long int i;
568  unsigned long int scale;
570  static const unsigned long int n_start = 63U;
572  static unsigned long int start[n_start];
574  static unsigned long int log(unsigned long int i);
576  static unsigned long int luby(unsigned long int i);
577  public:
579  CutoffLuby(unsigned long int scale);
581  virtual unsigned long int operator ()(void) const;
583  virtual unsigned long int operator ++(void);
584  };
585 
591  protected:
593  double n;
595  double scale;
597  double base;
598  public:
600  CutoffGeometric(unsigned long int scale, double base);
602  virtual unsigned long int operator ()(void) const;
604  virtual unsigned long int operator ++(void);
605  };
606 
612  protected:
616  unsigned long int min;
618  unsigned long int n;
620  unsigned long int step;
622  unsigned long int cur;
623  public:
625  CutoffRandom(unsigned int seed,
626  unsigned long int min, unsigned long int max,
627  unsigned long int n);
629  virtual unsigned long int operator ()(void) const;
631  virtual unsigned long int operator ++(void);
632  };
633 
639  protected:
645  unsigned long int n;
646  public:
648  CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
650  virtual unsigned long int operator ()(void) const;
652  virtual unsigned long int operator ++(void);
654  virtual ~CutoffAppend(void);
655  };
656 
662  protected:
667  public:
669  CutoffMerge(Cutoff* c1, Cutoff* c2);
671  virtual unsigned long int operator ()(void) const;
673  virtual unsigned long int operator ++(void);
675  virtual ~CutoffMerge(void);
676  };
677 
683  protected:
686  // Current cutoff
687  unsigned int cutoff;
688  // Iteration
689  unsigned long int i;
690  // Number of repetitions
691  unsigned long int n;
692  public:
694  CutoffRepeat(Cutoff* c, unsigned long int n);
696  virtual unsigned long int operator ()(void) const;
698  virtual unsigned long int operator ++(void);
700  virtual ~CutoffRepeat(void);
701  };
702 
703 }}
704 
705 #include <gecode/search/cutoff.hpp>
706 
707 namespace Gecode { namespace Search {
708 
709  class Stop;
710 
748  class Options {
749  public:
751  bool clone;
753  double threads;
755  unsigned int c_d;
757  unsigned int a_d;
759  unsigned int d_l;
761  unsigned int assets;
763  unsigned int slice;
765  unsigned int nogoods_limit;
775  Options(void);
778  expand(void) const;
779  };
780 
781 }}
782 
783 #include <gecode/search/options.hpp>
784 
785 namespace Gecode { namespace Search {
786 
802  public:
804 
805  Stop(void);
808  virtual bool stop(const Statistics& s, const Options& o) = 0;
810  virtual ~Stop(void);
812 
814  static Stop* node(unsigned long int l);
817  static Stop* fail(unsigned long int l);
819  static Stop* time(unsigned long int l);
821  };
822 
832  protected:
834  unsigned long int l;
835  public:
837  NodeStop(unsigned long int l);
839  unsigned long int limit(void) const;
841  void limit(unsigned long int l);
843  virtual bool stop(const Statistics& s, const Options& o);
844  };
845 
855  protected:
857  unsigned long int l;
858  public:
860  FailStop(unsigned long int l);
862  unsigned long int limit(void) const;
864  void limit(unsigned long int l);
866  virtual bool stop(const Statistics& s, const Options& o);
867  };
868 
874  protected:
878  unsigned long int l;
879  public:
881  TimeStop(unsigned long int l);
883  unsigned long int limit(void) const;
885  void limit(unsigned long int l);
887  void reset(void);
889  virtual bool stop(const Statistics& s, const Options& o);
890  };
891 
892 }}
893 
894 #include <gecode/search/stop.hpp>
895 
896 namespace Gecode { namespace Search {
897 
902  public:
904  virtual Space* next(void) = 0;
906  virtual Statistics statistics(void) const = 0;
908  virtual bool stopped(void) const = 0;
910  virtual void constrain(const Space& b);
912  virtual void reset(Space* s);
914  virtual NoGoods& nogoods(void);
916  virtual ~Engine(void);
917  };
918 
919 }}
920 
921 #include <gecode/search/engine.hpp>
922 
923 namespace Gecode { namespace Search {
924 
926  template<class T>
927  class Base : public HeapAllocated {
928  template<class, class>
929  friend Engine* build(Space*, const Options&);
930  template<class, template<class> class>
931  friend Engine* build(Space*, const Options&);
932  protected:
936  Base(Engine* e = NULL);
937  public:
939  virtual T* next(void);
941  virtual Statistics statistics(void) const;
943  virtual bool stopped(void) const;
945  virtual ~Base(void);
946  private:
948  Base(const Base&);
950  Base& operator =(const Base&);
951  };
952 
953 }}
954 
955 #include <gecode/search/base.hpp>
956 
957 namespace Gecode { namespace Search {
958 
960  template<class T, class E>
961  Engine* build(Space* s, const Options& opt);
963  template<class T, template<class> class E>
964  Engine* build(Space* s, const Options& opt);
965 
968  protected:
972  const bool b;
973  public:
975  Builder(const Options& opt, bool best);
977  Options& options(void);
979  const Options& options(void) const;
981  bool best(void) const;
983  virtual Engine* operator() (Space* s) const = 0;
985  virtual ~Builder(void);
986  };
987 
988 }}
989 
990 #include <gecode/search/build.hpp>
991 
992 namespace Gecode {
993 
996 
997 }
998 
999 #include <gecode/search/traits.hpp>
1000 
1001 namespace Gecode {
1002 
1004  class SEBs : public PrimArgArray<SEB> {
1005  public:
1007 
1008  SEBs(void);
1011  explicit SEBs(int n);
1013  SEBs(const std::vector<SEB>& x);
1015  template<class InputIterator>
1016  SEBs(InputIterator first, InputIterator last);
1018  SEBs(const PrimArgArray<SEB>& a);
1021  SEBs(int n, SEB b0, ...);
1023  };
1024 
1025 }
1026 
1027 #include <gecode/search/sebs.hpp>
1028 
1029 namespace Gecode {
1030 
1038  template<class T>
1039  class DFS : public Search::Base<T> {
1040  public:
1042  DFS(T* s, const Search::Options& o=Search::Options::def);
1044  static const bool best = false;
1045  };
1046 
1048  template<class T>
1049  T* dfs(T* s, const Search::Options& o=Search::Options::def);
1050 
1052  template<class T>
1054 
1055 }
1056 
1057 #include <gecode/search/dfs.hpp>
1058 
1059 namespace Gecode {
1060 
1072  template<class T>
1073  class BAB : public Search::Base<T> {
1074  public:
1076  BAB(T* s, const Search::Options& o=Search::Options::def);
1078  static const bool best = true;
1079  };
1080 
1093  template<class T>
1094  T* bab(T* s, const Search::Options& o=Search::Options::def);
1095 
1097  template<class T>
1099 
1100 }
1101 
1102 #include <gecode/search/bab.hpp>
1103 
1104 namespace Gecode {
1105 
1110  template<class T>
1111  class LDS : public Search::Base<T> {
1112  public:
1114  LDS(T* s, const Search::Options& o=Search::Options::def);
1116  static const bool best = false;
1117  };
1118 
1123  template<class T>
1124  T* lds(T* s, const Search::Options& o=Search::Options::def);
1125 
1127  template<class T>
1129 
1130 }
1131 
1132 #include <gecode/search/lds.hpp>
1133 
1134 namespace Gecode {
1135 
1154  template<class T, template<class> class E = DFS>
1155  class RBS : public Search::Base<T> {
1156  using Search::Base<T>::e;
1157  public:
1159  RBS(T* s, const Search::Options& o);
1161  static const bool best = E<T>::best;
1162  };
1163 
1182  template<class T, template<class> class E>
1183  T* rbs(T* s, const Search::Options& o);
1184 
1186  template<class T, template<class> class E>
1187  SEB rbs(const Search::Options& o);
1188 
1189 }
1190 
1191 #include <gecode/search/rbs.hpp>
1192 
1193 namespace Gecode { namespace Search { namespace Meta {
1194 
1196  template<class T, template<class> class E>
1197  Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
1198 
1200  template<class T, template<class> class E>
1201  Engine* sequential(T* master, SEBs& sebs,
1202  const Search::Statistics& stat, Options& opt, bool best);
1203 
1204 #ifdef GECODE_HAS_THREADS
1205 
1207  template<class T, template<class> class E>
1208  Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
1209 
1211  template<class T, template<class> class E>
1212  Engine* parallel(T* master, SEBs& sebs,
1213  const Search::Statistics& stat, Options& opt, bool best);
1214 
1215 #endif
1216 
1217 }}}
1218 
1219 namespace Gecode {
1220 
1238  template<class T, template<class> class E = DFS>
1239  class PBS : public Search::Base<T> {
1240  using Search::Base<T>::e;
1241  protected:
1243  void build(T* s, SEBs& sebs, const Search::Options& o);
1244  public:
1246  PBS(T* s, const Search::Options& o=Search::Options::def);
1248  PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
1250  PBS(T* s, SEB seb0, SEB seb1,
1253  PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
1256  PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
1259  static const bool best = E<T>::best;
1260  };
1261 
1279  template<class T, template<class> class E>
1280  T* pbs(T* s, const Search::Options& o=Search::Options::def);
1281 
1283  template<class T>
1285 
1286 }
1287 
1288 #include <gecode/search/pbs.hpp>
1289 
1290 #endif
1291 
1292 // STATISTICS: search-other
Edge information.
Definition: search.hh:244
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:757
double scale
Scale factor.
Definition: search.hh:595
const Space & _s
The corresponding space.
Definition: search.hh:293
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Definition: search.hh:295
Search engine implementation interface
Definition: search.hh:901
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:765
Limited discrepancy search engine.
Definition: search.hh:1111
unsigned long int scale
Scale factor.
Definition: search.hh:547
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Engine * parallel(T *master, SEBs &sebs, const Search::Statistics &stat, Options &opt, bool best)
Build a parallel engine.
Search engine statistics
Definition: search.hh:149
Class to send solution information to CPProfiler.
Definition: search.hh:425
Stop-object based on number of nodes
Definition: search.hh:831
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Meta-engine performing restart-based search.
Definition: search.hh:1155
Meta engine using a portfolio of search engines.
Definition: search.hh:1239
#define GECODE_SEARCH_EXPORT
Definition: search.hh:69
Node representing a branch.
Definition: spacenode.hh:51
Cutoff * c1
First cutoff generator.
Definition: search.hh:664
Argument array for primtive types.
Definition: array.hpp:628
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:755
Cutoff generator appending two cutoff generators.
Definition: search.hh:638
unsigned int _nid
The parent node id.
Definition: search.hh:249
Search engine options
Definition: search.hh:748
A class for building search engines.
Definition: search.hh:967
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
Options opt
Stored and already expanded options.
Definition: search.hh:970
unsigned long int l
Current limit in milliseconds.
Definition: search.hh:878
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
unsigned long int step
Step size.
Definition: search.hh:620
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition: build.hpp:62
std::string _s
String corresponding to alternative.
Definition: search.hh:253
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:122
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition: search.hh:763
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:45
unsigned long int scale
Scale factor.
Definition: search.hh:568
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
unsigned long int nogood
Number of no-goods posted.
Definition: search.hh:160
Support::Timer t
Time when execution should stop.
Definition: search.hh:876
Node representing failure.
Definition: spacenode.hh:50
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:156
Array with arbitrary number of elements.
Cutoff generator for the Luby sequence.
Definition: search.hh:563
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:474
unsigned long int min
Minimum cutoff value.
Definition: search.hh:616
Class to record search trace info for CPProfiler.
Definition: search.hh:422
EngineType
Which type of engine.
Definition: search.hh:195
unsigned long int c
Constant.
Definition: search.hh:530
Computation spaces.
Definition: core.hpp:1668
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:759
unsigned long int n
Random values.
Definition: search.hh:618
Statistics for execution of status
Definition: core.hpp:1617
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
Engine * sequential(T *master, SEBs &sebs, const Search::Statistics &stat, Options &opt, bool best)
Build a sequential engine.
std::string expand(Gecode::IntRelType irt)
Expand relation to abbreviation.
Definition: mm-count.cpp:48
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Definition: search.hh:661
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:769
double threads
Number of threads to use.
Definition: search.hh:753
const bool b
Whether engine to be built is a best solution search engine.
Definition: search.hh:972
const unsigned int cpprofiler_port
Default port for CPProfiler.
Definition: search.hh:136
Cutoff generator for the random sequence.
Definition: search.hh:611
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Recorder for a search tracer with edge information.
Options opt
The options.
Definition: test.cpp:101
Base-class for search engines.
Definition: search.hh:927
Depth-first branch-and-bound search engine.
Definition: search.hh:1073
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
Simple recorder for a search tracer.
static const Options def
Default options.
Definition: search.hh:773
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
Node representing a solution.
Definition: spacenode.hh:49
unsigned long int i
Definition: search.hh:689
unsigned long int n
How many number to take from the first.
Definition: search.hh:645
unsigned long int cur
Current value.
Definition: search.hh:622
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:614
EngineType _type
The engine type.
Definition: search.hh:207
unsigned long int i
Iteration number.
Definition: search.hh:566
double n
Current cutoff value.
Definition: search.hh:593
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
Template for linear congruential generators.
Definition: random.hpp:50
Search::Builder * SEB
Type for a search engine builder.
Definition: search.hh:995
const unsigned int d_l
Default discrepancy limit for LDS.
Definition: search.hh:125
unsigned int _a
Number of alternative.
Definition: search.hh:251
Cutoff * c2
Second cutoff generators.
Definition: search.hh:643
unsigned int _lst
Last worker or engine.
Definition: search.hh:211
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:771
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Definition: lds.hpp:78
Cutoff * c1
First cutoff generators.
Definition: search.hh:641
Cutoff generator for linear sequence.
Definition: search.hh:544
const double threads
Number of threads to use.
Definition: search.hh:112
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:77
Support for tracing search.
Definition: search.hh:189
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:761
Cutoff generator for the geometric sequence.
Definition: search.hh:590
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:81
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:334
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Cutoff * c
Actual cutoff generator.
Definition: search.hh:685
Cutoff generator for constant sequence.
Definition: search.hh:527
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
const double base
Base for geometric restart sequence.
Definition: search.hh:128
unsigned long int n
Next number in sequence.
Definition: search.hh:549
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
No-goods recorded from restarts.
Definition: core.hpp:1514
unsigned long int l
Node limit.
Definition: search.hh:834
Engine * e
The actual search engine.
Definition: search.hh:934
unsigned int _wid
The worker id.
Definition: search.hh:289
unsigned long int l
Failure limit.
Definition: search.hh:857
std::ostream & os
Output stream to use.
Definition: search.hh:376
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:682
Node information.
Definition: search.hh:284
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:115
Post propagator for SetVar x
Definition: set.hh:769
Recorder for engine events (for access control)
unsigned long int restart
Number of restarts.
Definition: search.hh:158
Passing search engine builder arguments.
Definition: search.hh:1004
NodeType
Node type.
Definition: search.hh:278
unsigned int _nid
The node id.
Definition: search.hh:291
Stop * stop
Stop object for stopping search.
Definition: search.hh:767
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:154
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:133
Information about an engine.
Definition: search.hh:204
unsigned long int n
Definition: search.hh:691
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Definition: search.hh:247
Stop-object based on time
Definition: search.hh:873
Base-class for Stop-object.
Definition: search.hh:801
Cutoff * c2
Second cutoff generator.
Definition: search.hh:666
NodeType _nt
The node type.
Definition: search.hh:287
Base class for heap allocated objects.
Definition: heap.hpp:344
static StdSearchTracer def
Default tracer (printing to std::cerr)
Definition: search.hh:395
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:120
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:115
Options for scripts
Definition: driver.hh:370
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Definition: search.hh:130
Depth-first search engine.
Definition: search.hh:1039
unsigned int _fst
First worker or engine.
Definition: search.hh:209
Stop-object based on number of failures
Definition: search.hh:854
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:110