Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
79namespace 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
141namespace Gecode { namespace Search {
142
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);
167 };
168
169}}
170
172
173namespace Gecode { namespace Search {
174
175 class WrapTraceRecorder;
176 class TraceRecorder;
177 class EdgeTraceRecorder;
178
179}}
180
181#include <string>
182#include <sstream>
183
184namespace Gecode {
185
191 public:
194 DFS = 0,
195 BAB = 1,
196 LDS = 2,
197 RBS = 3,
198 PBS = 4,
199 AOE = 5
200 };
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
218 EngineType type(void) const;
220 bool meta(void) const;
222
224
225 unsigned int wfst(void) const;
227 unsigned int wlst(void) const;
229 unsigned int workers(void) const;
231
233
234 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:
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:
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
346 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
357 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
368 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
400
401#ifdef GECODE_HAS_CPPROFILER
402
403namespace Gecode {
404
406 namespace CPProfiler {}
407
408}
409
410namespace Gecode { namespace CPProfiler {
411
413 class Connector;
414
415}}
416
417namespace 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
466namespace Gecode { namespace Search {
467
473 public:
475
476
477 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
488 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
704
705namespace 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
782
783namespace Gecode { namespace Search {
784
800 public:
802
803
804 Stop(void);
806 virtual bool stop(const Statistics& s, const Options& o) = 0;
808 virtual ~Stop(void);
810
812
813 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
894namespace 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
920
921namespace 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
955namespace 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
989
990namespace Gecode {
991
994
995}
996
998
999namespace Gecode {
1000
1002 class SEBs : public ArgArray<SEB> {
1003 public:
1005
1006
1007 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
1026namespace Gecode {
1027
1035 template<class T>
1036 class DFS : public Search::Base<T> {
1037 public:
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
1056namespace Gecode {
1057
1069 template<class T>
1070 class BAB : public Search::Base<T> {
1071 public:
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
1101namespace Gecode {
1102
1107 template<class T>
1108 class LDS : public Search::Base<T> {
1109 public:
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
1131namespace 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
1190namespace 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
1216namespace 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:
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
NNF * l
Left subtree.
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Argument array for non-primitive types.
Definition array.hpp:691
Depth-first branch-and-bound search engine.
Definition search.hh:1070
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition bab.hpp:72
static const bool best
Whether engine does best solution search.
Definition search.hh:1075
Class to send solution information to CPProfiler.
Definition search.hh:423
virtual std::string getInfo(const Space &home) const =0
Return info for a space.
Class to record search trace info for CPProfiler.
Definition search.hh:420
Choice for performing commit
Definition core.hpp:1412
Depth-first search engine.
Definition search.hh:1036
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
Definition dfs.hpp:68
static const bool best
Whether engine does best solution search.
Definition search.hh:1041
Base class for heap allocated objects.
Definition heap.hpp:340
Limited discrepancy search engine.
Definition search.hh:1108
static const bool best
Whether engine does best solution search.
Definition search.hh:1113
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition lds.hpp:69
No-goods recorded from restarts.
Definition core.hpp:1588
Meta engine using a portfolio of search engines.
Definition search.hh:1236
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition pbs.hpp:221
static const bool best
Whether engine does best solution search.
Definition search.hh:1247
Meta-engine performing restart-based search.
Definition search.hh:1152
static const bool best
Whether engine does best solution search.
Definition search.hh:1158
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition rbs.hpp:83
Passing search engine builder arguments.
Definition search.hh:1002
SEBs(void)
Allocate empty array.
Definition sebs.hpp:37
void invalidate(void)
Invalidate edge information (for stealing)
Definition tracer.hpp:102
unsigned int alternative(void) const
Return number of alternative.
Definition tracer.hpp:148
unsigned int _a
Number of alternative.
Definition search.hh:249
unsigned int _nid
The parent node id.
Definition search.hh:247
unsigned int wid(void) const
Return parent worker id.
Definition tracer.hpp:136
std::string string(void) const
Return string for alternative.
Definition tracer.hpp:154
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
EdgeInfo(void)
Initialize as non existing.
Definition tracer.hpp:127
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Definition search.hh:245
std::string _s
String corresponding to alternative.
Definition search.hh:251
Information about an engine.
Definition search.hh:202
bool meta(void) const
Return whether engine is a meta engine.
Definition tracer.hpp:56
unsigned int wfst(void) const
Return id of first worker.
Definition tracer.hpp:61
unsigned int _lst
Last worker or engine.
Definition search.hh:209
EngineInfo(void)
Do not initialize.
Definition tracer.hpp:43
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:75
EngineType _type
The engine type.
Definition search.hh:205
EngineType type(void) const
Return engine type.
Definition tracer.hpp:51
unsigned int efst(void) const
Return id of first engine.
Definition tracer.hpp:80
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:92
unsigned int _fst
First worker or engine.
Definition search.hh:207
unsigned int elst(void) const
Return id of last engine.
Definition tracer.hpp:86
unsigned int wlst(void) const
Return id of last worker plus one.
Definition tracer.hpp:68
unsigned int _wid
The worker id.
Definition search.hh:287
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Definition search.hh:293
NodeType _nt
The node type.
Definition search.hh:285
NodeType type(void) const
Return node type.
Definition tracer.hpp:171
const Choice & choice(void) const
Return corresponding choice.
Definition tracer.hpp:191
unsigned int nid(void) const
Return node id.
Definition tracer.hpp:181
unsigned int wid(void) const
Return worker id.
Definition tracer.hpp:176
const Space & space(void) const
Return corresponding space.
Definition tracer.hpp:186
unsigned int _nid
The node id.
Definition search.hh:289
const Space & _s
The corresponding space.
Definition search.hh:291
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition tracer.hpp:165
Support for tracing search.
Definition search.hh:187
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition tracer.hpp:278
NodeType
Node type.
Definition search.hh:276
@ FAILED
A solution node.
Definition search.hh:278
@ BRANCH
A failed node.
Definition search.hh:279
virtual void init(void)=0
The search engine initializes.
EngineType
Which type of engine.
Definition search.hh:193
@ AOE
Unspecified engine (any other engine)
Definition search.hh:199
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:266
virtual ~SearchTracer(void)
Delete.
Definition tracer.hpp:284
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS)
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:261
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
SearchTracer(void)
Initialize.
Definition tracer.hpp:220
virtual void done(void)=0
All workers are done.
Base-class for search engines.
Definition search.hh:925
Base(Engine *e=NULL)
Constructor.
Definition base.hpp:42
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition base.hpp:56
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition base.hpp:46
virtual Statistics statistics(void) const
Return statistics.
Definition base.hpp:51
virtual ~Base(void)
Destructor.
Definition base.hpp:61
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Definition build.hpp:58
Engine * e
The actual search engine.
Definition search.hh:932
A class for building search engines.
Definition search.hh:965
const bool b
Whether engine to be built is a best solution search engine.
Definition search.hh:970
Options opt
Stored and already expanded options.
Definition search.hh:968
Cutoff generator appending two cutoff generators.
Definition search.hh:636
unsigned long int n
How many number to take from the first.
Definition search.hh:643
Cutoff * c1
First cutoff generators.
Definition search.hh:639
Cutoff * c2
Second cutoff generators.
Definition search.hh:641
Cutoff generator for constant sequence.
Definition search.hh:525
unsigned long int c
Constant.
Definition search.hh:528
Cutoff generator for the geometric sequence.
Definition search.hh:588
double n
Current cutoff value.
Definition search.hh:591
double scale
Scale factor.
Definition search.hh:593
Cutoff generator for linear sequence.
Definition search.hh:542
unsigned long int n
Next number in sequence.
Definition search.hh:547
unsigned long int scale
Scale factor.
Definition search.hh:545
Cutoff generator for the Luby sequence.
Definition search.hh:561
unsigned long int scale
Scale factor.
Definition search.hh:566
unsigned long int i
Iteration number.
Definition search.hh:564
Cutoff generator merging two cutoff generators.
Definition search.hh:659
Cutoff * c1
First cutoff generator.
Definition search.hh:662
Cutoff * c2
Second cutoff generator.
Definition search.hh:664
Cutoff generator for the random sequence.
Definition search.hh:609
unsigned long int step
Step size.
Definition search.hh:618
unsigned long int cur
Current value.
Definition search.hh:620
unsigned long int n
Random values.
Definition search.hh:616
Support::RandomGenerator rnd
Random number generator.
Definition search.hh:612
unsigned long int min
Minimum cutoff value.
Definition search.hh:614
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition search.hh:680
Cutoff * c
Actual cutoff generator.
Definition search.hh:683
unsigned long int n
Definition search.hh:689
unsigned long int i
Definition search.hh:687
Base class for cutoff generators for restart-based meta engine.
Definition search.hh:472
Recorder for a search tracer with edge information.
Search engine implementation interface
Definition search.hh:899
virtual Statistics statistics(void) const =0
Return statistics.
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
virtual bool stopped(void) const =0
Check whether engine has been stopped.
Stop-object based on number of failures
Definition search.hh:852
unsigned long int l
Failure limit.
Definition search.hh:855
Stop-object based on number of nodes
Definition search.hh:829
unsigned long int l
Node limit.
Definition search.hh:832
Search engine options
Definition search.hh:746
static const Options def
Default options.
Definition search.hh:771
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition search.hh:753
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:749
Options(void)
Initialize with default values.
Definition options.hpp:37
unsigned int d_l
Discrepancy limit (for LDS)
Definition search.hh:757
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:767
Options expand(void) const
Expand with real number of threads.
Definition options.cpp:43
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition search.hh:755
Stop * stop
Stop object for stopping search.
Definition search.hh:765
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:769
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:759
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition search.hh:761
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition search.hh:763
double threads
Number of threads to use.
Definition search.hh:751
Search engine statistics
Definition search.hh:147
Statistics(void)
Initialize.
unsigned long int restart
Number of restarts.
Definition search.hh:156
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
unsigned long int depth
Maximum depth of search stack.
Definition search.hh:154
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
unsigned long int node
Number of nodes expanded.
Definition search.hh:152
Statistics operator+(const Statistics &s)
Return sum with s.
unsigned long int nogood
Number of no-goods posted.
Definition search.hh:158
Base-class for Stop-object.
Definition search.hh:799
virtual bool stop(const Statistics &s, const Options &o)=0
Stop search, if returns true.
Stop-object based on time
Definition search.hh:871
Support::Timer t
Time when execution should stop.
Definition search.hh:874
unsigned long int l
Current limit in milliseconds.
Definition search.hh:876
Simple recorder for a search tracer.
Recorder for engine events (for access control)
Computation spaces.
Definition core.hpp:1742
Statistics for execution of status
Definition core.hpp:1691
static StdSearchTracer def
Default tracer (printing to std::cerr)
Definition search.hh:393
std::ostream & os
Output stream to use.
Definition search.hh:374
Array with arbitrary number of elements.
Template for linear congruential generators.
Definition random.hpp:46
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:309
T * bab(T *s, const Search::Options &o=Search::Options::def)
Perform depth-first branch-and-bound search for subclass T of space s and options o.
Definition bab.hpp:77
T * lds(T *s, const Search::Options &o=Search::Options::def)
Invoke limited-discrepancy search for s as root node and optionso.
Definition lds.hpp:74
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:111
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:120
const unsigned int d_l
Default discrepancy limit for LDS.
Definition search.hh:123
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition search.hh:115
const double base
Base for geometric restart sequence.
Definition search.hh:126
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition search.hh:113
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
Definition search.hh:128
const unsigned int cpprofiler_port
Default port for CPProfiler.
Definition search.hh:134
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition search.hh:131
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition search.hh:118
const double threads
Number of threads to use.
Definition search.hh:110
const bool clone
Whether engines create a clone when being initialized.
Definition search.hh:108
Engine * sequential(T *master, const Search::Statistics &stat, Options &opt)
Build a sequential engine.
Engine * parallel(T *master, const Search::Statistics &stat, Options &opt)
Build a parallel engine.
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition build.hpp:58
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
Definition search.hh:993
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
Post propagator for SetVar x
Definition set.hh:767
#define GECODE_SEARCH_EXPORT
Definition search.hh:67