Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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 };
201
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 };
241
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 };
275
276 enum NodeType {
277 SOLVED = 0,
278 FAILED = 1,
280 };
281
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:
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
794
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
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.
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
Definition tracer.cpp:99
virtual void init(void)
The search engine initializes.
Definition tracer.cpp:62
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
Definition tracer.cpp:77
virtual void round(unsigned int eid)
The engine with id eid goes to a next round (restart or next iteration in LDS)
Definition tracer.cpp:71
virtual void done(void)
All workers are done.
Definition tracer.cpp:148
CPProfilerSearchTracer(int eid, std::string name, unsigned int port=Search::Config::cpprofiler_port, const GetInfo *pgi=nullptr)
Initialize.
Definition tracer.cpp:54
Choice for performing commit
Definition core.hpp:1414
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
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:1590
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition pbs.hpp:262
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
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
@ BAB
Engine is a BAB engine.
Definition search.hh:195
@ DFS
Engine is a DFS engine.
Definition search.hh:194
@ AOE
Unspecified engine (any other engine)
Definition search.hh:199
@ PBS
Engine is a PBS engine.
Definition search.hh:198
@ RBS
Engine is a RBS engine.
Definition search.hh:197
@ LDS
Engine is a LDS engine.
Definition search.hh:196
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
Builder(const Options &opt, bool best)
Initialize with options opt and best solution search support.
Definition build.hpp:37
bool best(void) const
Whether engine is a best solution search engine.
Definition build.hpp:48
Options & options(void)
Provide access to options.
Definition build.hpp:40
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
CutoffAppend(Cutoff *c1, unsigned long int n, Cutoff *c2)
Constructor.
Definition cutoff.hpp:100
unsigned long int c
Constant.
Definition search.hh:528
CutoffConstant(unsigned long int c)
Constructor.
Definition cutoff.hpp:47
double n
Current cutoff value.
Definition search.hh:591
CutoffGeometric(unsigned long int scale, double base)
Constructor.
Definition cutoff.hpp:83
double scale
Scale factor.
Definition search.hh:593
unsigned long int n
Next number in sequence.
Definition search.hh:547
CutoffLinear(unsigned long int scale)
Constructor.
Definition cutoff.hpp:52
unsigned long int scale
Scale factor.
Definition search.hh:545
static unsigned long int luby(unsigned long int i)
Compute Luby number for step i.
Definition cutoff.hpp:68
static const unsigned long int n_start
Number of pre-computed luby values.
Definition search.hh:568
CutoffLuby(unsigned long int scale)
Constructor.
Definition cutoff.hpp:57
static unsigned long int log(unsigned long int i)
Compute binary logarithm of i.
Definition cutoff.hpp:60
unsigned long int scale
Scale factor.
Definition search.hh:566
unsigned long int i
Iteration number.
Definition search.hh:564
static unsigned long int start[n_start]
Precomputed luby-values.
Definition search.hh:570
Cutoff * c1
First cutoff generator.
Definition search.hh:662
Cutoff * c2
Second cutoff generator.
Definition search.hh:664
CutoffMerge(Cutoff *c1, Cutoff *c2)
Constructor.
Definition cutoff.hpp:109
unsigned long int step
Step size.
Definition search.hh:618
unsigned long int cur
Current value.
Definition search.hh:620
CutoffRandom(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Constructor.
Definition cutoff.hpp:88
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
CutoffRepeat(Cutoff *c, unsigned long int n)
Constructor.
Definition cutoff.hpp:118
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
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Definition cutoff.cpp:164
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
Definition cutoff.cpp:175
static Cutoff * linear(unsigned long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
Definition cutoff.cpp:152
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition cutoff.cpp:148
Cutoff(void)
Default constructor.
Definition cutoff.hpp:41
static Cutoff * luby(unsigned long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
Definition cutoff.cpp:156
static Cutoff * append(Cutoff *c1, unsigned long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
Definition cutoff.cpp:171
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Definition cutoff.cpp:179
Recorder for a search tracer with edge information.
Search engine implementation interface
Definition search.hh:899
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception)
Definition engine.cpp:39
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 void reset(Space *s)
Reset engine to restart at space s (does nothing)
Definition engine.cpp:44
virtual bool stopped(void) const =0
Check whether engine has been stopped.
virtual NoGoods & nogoods(void)
Return no-goods (the no-goods are empty)
Definition engine.cpp:48
unsigned long int l
Failure limit.
Definition search.hh:855
FailStop(unsigned long int l)
Stop if failure limit l is exceeded.
Definition stop.hpp:71
unsigned long int limit(void) const
Return current limit.
Definition stop.hpp:74
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition stop.cpp:71
unsigned long int limit(void) const
Return current limit.
Definition stop.hpp:55
NodeStop(unsigned long int l)
Stop if node limit l is exceeded.
Definition stop.hpp:52
unsigned long int l
Node limit.
Definition search.hh:832
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
Definition stop.cpp:61
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
Stop(void)
Default constructor.
Definition stop.hpp:41
static Stop * node(unsigned long int l)
Stop if node limit l has been exceeded.
Definition stop.cpp:43
static Stop * time(unsigned long int l)
Stop if time limit l (in milliseconds) has been exceeded.
Definition stop.cpp:51
virtual bool stop(const Statistics &s, const Options &o)=0
Stop search, if returns true.
static Stop * fail(unsigned long int l)
Stop if failure limit l has been exceeded.
Definition stop.cpp:47
virtual bool stop(const Statistics &s, const Options &o)
Return true if time limit is exceeded.
Definition stop.cpp:81
unsigned long int limit(void) const
Return current limit in milliseconds.
Definition stop.hpp:96
TimeStop(unsigned long int l)
Stop if search exceeds l milliseconds (from creation of this object)
Definition stop.hpp:90
Support::Timer t
Time when execution should stop.
Definition search.hh:874
unsigned long int l
Current limit in milliseconds.
Definition search.hh:876
void reset(void)
Reset time to zero.
Definition stop.hpp:106
Simple recorder for a search tracer.
Recorder for engine events (for access control)
Computation spaces.
Definition core.hpp:1744
StatusStatistics(void)
Initialize.
Definition core.hpp:4701
static const char * t2s[EngineType::AOE+1]
Map engine type to string.
Definition search.hh:376
StdSearchTracer(std::ostream &os=std::cerr)
Initialize with output stream os.
Definition tracer.cpp:45
virtual void done(void)
All workers are done.
Definition tracer.cpp:113
virtual void init(void)
The search engine initializes.
Definition tracer.cpp:49
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
Definition tracer.cpp:82
static StdSearchTracer def
Default tracer (printing to std::cerr)
Definition search.hh:393
virtual void round(unsigned int eid)
The engine with id eid goes to a next round (restart or next iteration in LDS)
Definition tracer.cpp:70
std::ostream & os
Output stream to use.
Definition search.hh:374
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
Definition tracer.cpp:75
Array with arbitrary number of elements.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:120
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
Code that is specific to the CPProfiler.
Definition search.hh:406
Search configuration
Definition search.hh:106
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
Parallel meta search engine implementations
Definition search.hh:96
Sequential meta search engine implementations
Definition search.hh:93
Meta search engine implementations
Definition search.hh:88
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.
Parallel search engine implementations
Definition search.hh:85
Sequential search engine implementations
Definition search.hh:82
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 min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
#define GECODE_SEARCH_EXPORT
Definition search.hh:67