Generated on Sat Jun 2 2018 07:17:44 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  * 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 <gecode/kernel.hh>
46 
47 /*
48  * Configure linking
49  *
50  */
51 #if !defined(GECODE_STATIC_LIBS) && \
52  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
53 
54 #ifdef GECODE_BUILD_SEARCH
55 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
56 #else
57 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
58 #endif
59 
60 #else
61 
62 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
63 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
64 #else
65 #define GECODE_SEARCH_EXPORT
66 #endif
67 
68 #endif
69 
70 // Configure auto-linking
71 #ifndef GECODE_BUILD_SEARCH
72 #define GECODE_LIBRARY_NAME "Search"
74 #endif
75 
76 
77 namespace Gecode { namespace Search {
78 
80  namespace Sequential {}
81 
83  namespace Parallel {}
84 
86  namespace Meta {}
87 
88  namespace Meta {
89 
91  namespace Sequential {}
92 
94  namespace Parallel {}
95 
96  }
97 
98 
104  namespace Config {
106  const bool clone = true;
108  const double threads = 1.0;
109 
111  const unsigned int c_d = 8;
113  const unsigned int a_d = 2;
114 
116  const unsigned int steal_limit = 3;
118  const unsigned int initial_delay = 5;
119 
121  const unsigned int d_l = 5;
122 
124  const double base = 1.5;
126  const unsigned int slice = 250;
127 
129  const unsigned int nogoods_limit = 128;
130 
132  const unsigned int cpprofiler_port = 6565U;
133  }
134 
135 }}
136 
138 
139 namespace Gecode { namespace Search {
140 
145  class Statistics : public StatusStatistics {
146  public:
148  unsigned long int fail;
150  unsigned long int node;
152  unsigned long int depth;
154  unsigned long int restart;
156  unsigned long int nogood;
158  Statistics(void);
160  void reset(void);
162  Statistics operator +(const Statistics& s);
164  Statistics& operator +=(const Statistics& s);
165  };
166 
167 }}
168 
170 
171 namespace Gecode { namespace Search {
172 
173  class WrapTraceRecorder;
174  class TraceRecorder;
175  class EdgeTraceRecorder;
176 
177 }}
178 
179 #include <string>
180 #include <sstream>
181 
182 namespace Gecode {
183 
185  class SearchTracer {
187  friend class Search::TraceRecorder;
189  public:
191  enum EngineType {
192  DFS = 0,
193  BAB = 1,
194  LDS = 2,
195  RBS = 3,
196  PBS = 4,
197  AOE = 5
198  };
200  class EngineInfo {
201  protected:
205  unsigned int _fst;
207  unsigned int _lst;
208  public:
210  EngineInfo(void);
212  EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
214 
215  EngineType type(void) const;
218  bool meta(void) const;
220 
222  unsigned int wfst(void) const;
225  unsigned int wlst(void) const;
227  unsigned int workers(void) const;
229 
231  unsigned int efst(void) const;
234  unsigned int elst(void) const;
236  unsigned int engines(void) const;
238  };
240  class EdgeInfo {
241  protected:
243  unsigned int _wid;
245  unsigned int _nid;
247  unsigned int _a;
249  std::string _s;
250  public:
252  void init(unsigned int wid, unsigned int nid, unsigned int a);
254  void init(unsigned int wid, unsigned int nid, unsigned int a,
255  const Space& s, const Choice & c);
257  void invalidate(void);
259  EdgeInfo(void);
261  EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
263  operator bool(void) const;
265  unsigned int wid(void) const;
267  unsigned int nid(void) const;
269  unsigned int alternative(void) const;
271  std::string string(void) const;
272  };
274  enum NodeType {
275  SOLVED = 0,
276  FAILED = 1,
277  BRANCH = 2
278  };
280  class NodeInfo {
281  protected:
285  unsigned int _wid;
287  unsigned int _nid;
289  const Space& _s;
291  const Choice* _c;
292  public:
294  NodeInfo(NodeType nt,
295  unsigned int wid, unsigned int nid,
296  const Space& s, const Choice* c = nullptr);
298  NodeType type(void) const;
300  unsigned int wid(void) const;
302  unsigned int nid(void) const;
304  const Space& space(void) const;
306  const Choice& choice(void) const;
307  };
308  private:
310  Support::Mutex m;
312  unsigned int pending;
314  unsigned int n_e;
316  unsigned int n_w;
318  unsigned int n_active;
324  void engine(EngineType t, unsigned int n);
326  void worker(unsigned int& wid, unsigned int& eid);
328  void worker(void);
330  //{@
332  void _round(unsigned int eid);
334  void _skip(const EdgeInfo& ei);
336  void _node(const EdgeInfo& ei, const NodeInfo& ni);
338  public:
340  SearchTracer(void);
342 
343  unsigned int workers(void) const;
346  unsigned int engines(void) const;
348  const EngineInfo& engine(unsigned int eid) const;
350  unsigned int eid(unsigned int wid) const;
352 
354  virtual void init(void) = 0;
357  virtual void round(unsigned int eid) = 0;
359  virtual void skip(const EdgeInfo& ei) = 0;
361  virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
363  virtual void done(void) = 0;
365  virtual ~SearchTracer(void);
367  };
368 
370  protected:
372  std::ostream& os;
374  static const char* t2s[EngineType::AOE + 1];
375  public:
377  StdSearchTracer(std::ostream& os = std::cerr);
379  virtual void init(void);
381  virtual void round(unsigned int eid);
383  virtual void skip(const EdgeInfo& ei);
385  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
387  virtual void done(void);
389  virtual ~StdSearchTracer(void);
392  };
393 
394 }
395 
396 #include <gecode/search/tracer.hpp>
398 
399 #ifdef GECODE_HAS_CPPROFILER
400 
401 namespace Gecode {
402 
404  namespace CPProfiler {}
405 
406 }
407 
408 namespace Gecode { namespace CPProfiler {
409 
411  class Connector;
412 
413 }}
414 
415 namespace Gecode {
416 
419  public:
422  public:
424  GetInfo(void);
426  virtual std::string getInfo(const Space& home) const = 0;
428  virtual ~GetInfo(void);
429  };
430  private:
432  CPProfiler::Connector* connector;
434  int execution_id;
436  std::string name;
438  int restart;
440  const GetInfo* pgi;
441  public:
443  CPProfilerSearchTracer(int eid, std::string name,
444  unsigned int port = Search::Config::cpprofiler_port,
445  const GetInfo* pgi = nullptr);
447  virtual void init(void);
449  virtual void round(unsigned int eid);
451  virtual void skip(const EdgeInfo& ei);
453  virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
455  virtual void done(void);
457  virtual ~CPProfilerSearchTracer(void);
458  };
459 
460 }
461 
462 #endif
463 
464 namespace Gecode { namespace Search {
465 
471  public:
473 
474  Cutoff(void);
477  virtual unsigned long int operator ()(void) const = 0;
479  virtual unsigned long int operator ++(void) = 0;
481  virtual ~Cutoff(void);
483 
485  static Cutoff*
487  constant(unsigned long int scale=Config::slice);
489  static Cutoff*
490  linear(unsigned long int scale=Config::slice);
494  static Cutoff*
495  geometric(unsigned long int scale=Config::slice, double base=Config::base);
497  static Cutoff*
498  luby(unsigned long int scale=Config::slice);
503  static Cutoff*
504  rnd(unsigned int seed,
505  unsigned long int min, unsigned long int max,
506  unsigned long int n);
508  static Cutoff*
509  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
511  static Cutoff*
512  merge(Cutoff* c1, Cutoff* c2);
514  static Cutoff*
515  repeat(Cutoff* c, unsigned long int n);
517  };
518 
524  protected:
526  unsigned long int c;
527  public:
529  CutoffConstant(unsigned long int c);
531  virtual unsigned long int operator ()(void) const;
533  virtual unsigned long int operator ++(void);
534  };
535 
541  protected:
543  unsigned long int scale;
545  unsigned long int n;
546  public:
548  CutoffLinear(unsigned long int scale);
550  virtual unsigned long int operator ()(void) const;
552  virtual unsigned long int operator ++(void);
553  };
554 
560  protected:
562  unsigned long int i;
564  unsigned long int scale;
566  static const unsigned long int n_start = 63U;
568  static unsigned long int start[n_start];
570  static unsigned long int log(unsigned long int i);
572  static unsigned long int luby(unsigned long int i);
573  public:
575  CutoffLuby(unsigned long int scale);
577  virtual unsigned long int operator ()(void) const;
579  virtual unsigned long int operator ++(void);
580  };
581 
587  protected:
589  double n;
591  double scale;
593  double base;
594  public:
596  CutoffGeometric(unsigned long int scale, double base);
598  virtual unsigned long int operator ()(void) const;
600  virtual unsigned long int operator ++(void);
601  };
602 
608  protected:
612  unsigned long int min;
614  unsigned long int n;
616  unsigned long int step;
618  unsigned long int cur;
619  public:
621  CutoffRandom(unsigned int seed,
622  unsigned long int min, unsigned long int max,
623  unsigned long int n);
625  virtual unsigned long int operator ()(void) const;
627  virtual unsigned long int operator ++(void);
628  };
629 
635  protected:
641  unsigned long int n;
642  public:
644  CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
646  virtual unsigned long int operator ()(void) const;
648  virtual unsigned long int operator ++(void);
650  virtual ~CutoffAppend(void);
651  };
652 
658  protected:
663  public:
665  CutoffMerge(Cutoff* c1, Cutoff* c2);
667  virtual unsigned long int operator ()(void) const;
669  virtual unsigned long int operator ++(void);
671  virtual ~CutoffMerge(void);
672  };
673 
679  protected:
682  // Current cutoff
683  unsigned int cutoff;
684  // Iteration
685  unsigned long int i;
686  // Number of repetitions
687  unsigned long int n;
688  public:
690  CutoffRepeat(Cutoff* c, unsigned long int n);
692  virtual unsigned long int operator ()(void) const;
694  virtual unsigned long int operator ++(void);
696  virtual ~CutoffRepeat(void);
697  };
698 
699 }}
700 
701 #include <gecode/search/cutoff.hpp>
702 
703 namespace Gecode { namespace Search {
704 
705  class Stop;
706 
744  class Options {
745  public:
747  bool clone;
749  double threads;
751  unsigned int c_d;
753  unsigned int a_d;
755  unsigned int d_l;
757  unsigned int assets;
759  unsigned int slice;
761  unsigned int nogoods_limit;
771  Options(void);
774  expand(void) const;
775  };
776 
777 }}
778 
779 #include <gecode/search/options.hpp>
780 
781 namespace Gecode { namespace Search {
782 
798  public:
800 
801  Stop(void);
804  virtual bool stop(const Statistics& s, const Options& o) = 0;
806  virtual ~Stop(void);
808 
810  static Stop* node(unsigned long int l);
813  static Stop* fail(unsigned long int l);
815  static Stop* time(unsigned long int l);
817  };
818 
828  protected:
830  unsigned long int l;
831  public:
833  NodeStop(unsigned long int l);
835  unsigned long int limit(void) const;
837  void limit(unsigned long int l);
839  virtual bool stop(const Statistics& s, const Options& o);
840  };
841 
851  protected:
853  unsigned long int l;
854  public:
856  FailStop(unsigned long int l);
858  unsigned long int limit(void) const;
860  void limit(unsigned long int l);
862  virtual bool stop(const Statistics& s, const Options& o);
863  };
864 
870  protected:
874  unsigned long int l;
875  public:
877  TimeStop(unsigned long int l);
879  unsigned long int limit(void) const;
881  void limit(unsigned long int l);
883  void reset(void);
885  virtual bool stop(const Statistics& s, const Options& o);
886  };
887 
888 }}
889 
890 #include <gecode/search/stop.hpp>
891 
892 namespace Gecode { namespace Search {
893 
898  public:
900  virtual Space* next(void) = 0;
902  virtual Statistics statistics(void) const = 0;
904  virtual bool stopped(void) const = 0;
906  virtual void constrain(const Space& b);
908  virtual void reset(Space* s);
910  virtual NoGoods& nogoods(void);
912  virtual ~Engine(void);
913  };
914 
915 }}
916 
917 #include <gecode/search/engine.hpp>
918 
919 namespace Gecode { namespace Search {
920 
922  template<class T>
923  class Base : public HeapAllocated {
924  template<class, class>
925  friend Engine* build(Space*, const Options&);
926  template<class, template<class> class>
927  friend Engine* build(Space*, const Options&);
928  protected:
932  Base(Engine* e = NULL);
933  public:
935  virtual T* next(void);
937  virtual Statistics statistics(void) const;
939  virtual bool stopped(void) const;
941  virtual ~Base(void);
942  private:
944  Base(const Base&);
946  Base& operator =(const Base&);
947  };
948 
949 }}
950 
951 #include <gecode/search/base.hpp>
952 
953 namespace Gecode { namespace Search {
954 
956  template<class T, class E>
957  Engine* build(Space* s, const Options& opt);
959  template<class T, template<class> class E>
960  Engine* build(Space* s, const Options& opt);
961 
964  protected:
968  const bool b;
969  public:
971  Builder(const Options& opt, bool best);
973  Options& options(void);
975  const Options& options(void) const;
977  bool best(void) const;
979  virtual Engine* operator() (Space* s) const = 0;
981  virtual ~Builder(void);
982  };
983 
984 }}
985 
986 #include <gecode/search/build.hpp>
987 
988 namespace Gecode {
989 
992 
993 }
994 
995 #include <gecode/search/traits.hpp>
996 
997 namespace Gecode {
998 
1000  class SEBs : public PrimArgArray<SEB> {
1001  public:
1003 
1004  SEBs(void);
1007  explicit SEBs(int n);
1009  SEBs(const std::vector<SEB>& x);
1011  template<class InputIterator>
1012  SEBs(InputIterator first, InputIterator last);
1014  SEBs(const PrimArgArray<SEB>& a);
1017  SEBs(int n, SEB b0, ...);
1019  };
1020 
1021 }
1022 
1023 #include <gecode/search/sebs.hpp>
1024 
1025 namespace Gecode {
1026 
1034  template<class T>
1035  class DFS : public Search::Base<T> {
1036  public:
1038  DFS(T* s, const Search::Options& o=Search::Options::def);
1040  static const bool best = false;
1041  };
1042 
1044  template<class T>
1045  T* dfs(T* s, const Search::Options& o=Search::Options::def);
1046 
1048  template<class T>
1050 
1051 }
1052 
1053 #include <gecode/search/dfs.hpp>
1054 
1055 namespace Gecode {
1056 
1068  template<class T>
1069  class BAB : public Search::Base<T> {
1070  public:
1072  BAB(T* s, const Search::Options& o=Search::Options::def);
1074  static const bool best = true;
1075  };
1076 
1089  template<class T>
1090  T* bab(T* s, const Search::Options& o=Search::Options::def);
1091 
1093  template<class T>
1095 
1096 }
1097 
1098 #include <gecode/search/bab.hpp>
1099 
1100 namespace Gecode {
1101 
1106  template<class T>
1107  class LDS : public Search::Base<T> {
1108  public:
1110  LDS(T* s, const Search::Options& o=Search::Options::def);
1112  static const bool best = false;
1113  };
1114 
1119  template<class T>
1120  T* lds(T* s, const Search::Options& o=Search::Options::def);
1121 
1123  template<class T>
1125 
1126 }
1127 
1128 #include <gecode/search/lds.hpp>
1129 
1130 namespace Gecode {
1131 
1150  template<class T, template<class> class E = DFS>
1151  class RBS : public Search::Base<T> {
1152  using Search::Base<T>::e;
1153  public:
1155  RBS(T* s, const Search::Options& o);
1157  static const bool best = E<T>::best;
1158  };
1159 
1178  template<class T, template<class> class E>
1179  T* rbs(T* s, const Search::Options& o);
1180 
1182  template<class T, template<class> class E>
1183  SEB rbs(const Search::Options& o);
1184 
1185 }
1186 
1187 #include <gecode/search/rbs.hpp>
1188 
1189 namespace Gecode { namespace Search { namespace Meta {
1190 
1192  template<class T, template<class> class E>
1193  Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
1194 
1196  template<class T, template<class> class E>
1197  Engine* sequential(T* master, SEBs& sebs,
1198  const Search::Statistics& stat, Options& opt, bool best);
1199 
1200 #ifdef GECODE_HAS_THREADS
1201 
1203  template<class T, template<class> class E>
1204  Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
1205 
1207  template<class T, template<class> class E>
1208  Engine* parallel(T* master, SEBs& sebs,
1209  const Search::Statistics& stat, Options& opt, bool best);
1210 
1211 #endif
1212 
1213 }}}
1214 
1215 namespace Gecode {
1216 
1234  template<class T, template<class> class E = DFS>
1235  class PBS : public Search::Base<T> {
1236  using Search::Base<T>::e;
1237  protected:
1239  void build(T* s, SEBs& sebs, const Search::Options& o);
1240  public:
1242  PBS(T* s, const Search::Options& o=Search::Options::def);
1244  PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
1246  PBS(T* s, SEB seb0, SEB seb1,
1249  PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
1252  PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
1255  static const bool best = E<T>::best;
1256  };
1257 
1275  template<class T, template<class> class E>
1276  T* pbs(T* s, const Search::Options& o=Search::Options::def);
1277 
1279  template<class T>
1281 
1282 }
1283 
1284 #include <gecode/search/pbs.hpp>
1285 
1286 #endif
1287 
1288 // STATISTICS: search-other
Edge information.
Definition: search.hh:240
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:753
double scale
Scale factor.
Definition: search.hh:591
const Space & _s
The corresponding space.
Definition: search.hh:289
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Definition: search.hh:291
Search engine implementation interface
Definition: search.hh:897
NodeType t
Type of node.
Definition: bool-expr.cpp:230
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:761
Limited discrepancy search engine.
Definition: search.hh:1107
unsigned long int scale
Scale factor.
Definition: search.hh:543
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Engine * parallel(T *master, SEBs &sebs, const Search::Statistics &stat, Options &opt, bool best)
Build a parallel engine.
Search engine statistics
Definition: search.hh:145
Class to send solution information to CPProfiler.
Definition: search.hh:421
Stop-object based on number of nodes
Definition: search.hh:827
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Meta-engine performing restart-based search.
Definition: search.hh:1151
Meta engine using a portfolio of search engines.
Definition: search.hh:1235
#define GECODE_SEARCH_EXPORT
Definition: search.hh:65
Node representing a branch.
Definition: spacenode.hh:47
Cutoff * c1
First cutoff generator.
Definition: search.hh:660
Argument array for primtive types.
Definition: array.hpp:624
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:751
Cutoff generator appending two cutoff generators.
Definition: search.hh:634
unsigned int _nid
The parent node id.
Definition: search.hh:245
Search engine options
Definition: search.hh:744
A class for building search engines.
Definition: search.hh:963
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Options opt
Stored and already expanded options.
Definition: search.hh:966
unsigned long int l
Current limit in milliseconds.
Definition: search.hh:874
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
unsigned long int step
Step size.
Definition: search.hh:616
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition: build.hpp:58
std::string _s
String corresponding to alternative.
Definition: search.hh:249
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:118
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition: search.hh:759
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
unsigned long int scale
Scale factor.
Definition: search.hh:564
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:148
unsigned long int nogood
Number of no-goods posted.
Definition: search.hh:156
Support::Timer t
Time when execution should stop.
Definition: search.hh:872
Node representing failure.
Definition: spacenode.hh:46
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:152
Array with arbitrary number of elements.
Cutoff generator for the Luby sequence.
Definition: search.hh:559
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:470
unsigned long int min
Minimum cutoff value.
Definition: search.hh:612
Class to record search trace info for CPProfiler.
Definition: search.hh:418
EngineType
Which type of engine.
Definition: search.hh:191
unsigned long int c
Constant.
Definition: search.hh:526
Computation spaces.
Definition: core.hpp:1701
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:755
unsigned long int n
Random values.
Definition: search.hh:614
Statistics for execution of status
Definition: core.hpp:1650
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
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:44
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Definition: search.hh:657
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:765
double threads
Number of threads to use.
Definition: search.hh:749
const bool b
Whether engine to be built is a best solution search engine.
Definition: search.hh:968
const unsigned int cpprofiler_port
Default port for CPProfiler.
Definition: search.hh:132
Cutoff generator for the random sequence.
Definition: search.hh:607
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Recorder for a search tracer with edge information.
Options opt
The options.
Definition: test.cpp:97
Base-class for search engines.
Definition: search.hh:923
Depth-first branch-and-bound search engine.
Definition: search.hh:1069
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:164
Simple recorder for a search tracer.
static const Options def
Default options.
Definition: search.hh:769
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:113
Node representing a solution.
Definition: spacenode.hh:45
unsigned long int i
Definition: search.hh:685
unsigned long int n
How many number to take from the first.
Definition: search.hh:641
unsigned long int cur
Current value.
Definition: search.hh:618
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:610
EngineType _type
The engine type.
Definition: search.hh:203
unsigned long int i
Iteration number.
Definition: search.hh:562
double n
Current cutoff value.
Definition: search.hh:589
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:747
Template for linear congruential generators.
Definition: random.hpp:46
Search::Builder * SEB
Type for a search engine builder.
Definition: search.hh:991
const unsigned int d_l
Default discrepancy limit for LDS.
Definition: search.hh:121
unsigned int _a
Number of alternative.
Definition: search.hh:247
Cutoff * c2
Second cutoff generators.
Definition: search.hh:639
unsigned int _lst
Last worker or engine.
Definition: search.hh:207
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:767
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Definition: lds.hpp:74
Cutoff * c1
First cutoff generators.
Definition: search.hh:637
Cutoff generator for linear sequence.
Definition: search.hh:540
const double threads
Number of threads to use.
Definition: search.hh:108
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
Support for tracing search.
Definition: search.hh:185
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:757
Cutoff generator for the geometric sequence.
Definition: search.hh:586
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
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:330
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Cutoff * c
Actual cutoff generator.
Definition: search.hh:681
Cutoff generator for constant sequence.
Definition: search.hh:523
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
const double base
Base for geometric restart sequence.
Definition: search.hh:124
unsigned long int n
Next number in sequence.
Definition: search.hh:545
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1371
No-goods recorded from restarts.
Definition: core.hpp:1547
unsigned long int l
Node limit.
Definition: search.hh:830
Engine * e
The actual search engine.
Definition: search.hh:930
unsigned int _wid
The worker id.
Definition: search.hh:285
unsigned long int l
Failure limit.
Definition: search.hh:853
std::ostream & os
Output stream to use.
Definition: search.hh:372
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:678
Node information.
Definition: search.hh:280
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:111
Post propagator for SetVar x
Definition: set.hh:765
Recorder for engine events (for access control)
unsigned long int restart
Number of restarts.
Definition: search.hh:154
Passing search engine builder arguments.
Definition: search.hh:1000
NodeType
Node type.
Definition: search.hh:274
unsigned int _nid
The node id.
Definition: search.hh:287
Stop * stop
Stop object for stopping search.
Definition: search.hh:763
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:150
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:129
Information about an engine.
Definition: search.hh:200
unsigned long int n
Definition: search.hh:687
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Definition: search.hh:243
Stop-object based on time
Definition: search.hh:869
Base-class for Stop-object.
Definition: search.hh:797
Cutoff * c2
Second cutoff generator.
Definition: search.hh:662
NodeType _nt
The node type.
Definition: search.hh:283
Base class for heap allocated objects.
Definition: heap.hpp:340
static StdSearchTracer def
Default tracer (printing to std::cerr)
Definition: search.hh:391
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:116
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:111
Options for scripts
Definition: driver.hh:366
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Definition: search.hh:126
Depth-first search engine.
Definition: search.hh:1035
unsigned int _fst
First worker or engine.
Definition: search.hh:205
Stop-object based on number of failures
Definition: search.hh:850
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:106