Generated on for Gecode by doxygen 1.18.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.dev>
5 * Guido Tack <tack@gecode.dev>
6 *
7 * Contributing authors:
8 * Kevin Leo <kevin.leo@monash.edu>
9 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
10 * Maxim Shishmarev <maxim.shishmarev@monash.edu>
11 *
12 * Copyright:
13 * Kevin Leo, 2017
14 * Christian Schulte, 2002
15 * Mikael Zayenz Lagerkvist, 2026
16 * Maxim Shishmarev, 2017
17 * Guido Tack, 2004
18 *
19 * This file is part of Gecode, the generic constraint
20 * development environment:
21 * http://www.gecode.dev
22 *
23 * Permission is hereby granted, free of charge, to any person obtaining
24 * a copy of this software and associated documentation files (the
25 * "Software"), to deal in the Software without restriction, including
26 * without limitation the rights to use, copy, modify, merge, publish,
27 * distribute, sublicense, and/or sell copies of the Software, and to
28 * permit persons to whom the Software is furnished to do so, subject to
29 * the following conditions:
30 *
31 * The above copyright notice and this permission notice shall be
32 * included in all copies or substantial portions of the Software.
33 *
34 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41 *
42 */
43
44#ifndef GECODE_SEARCH_HH
45#define GECODE_SEARCH_HH
46
47#include <chrono>
48#include <initializer_list>
49#include <atomic>
50#ifdef GECODE_HAS_EXPERIMENTAL
51#include <cstdint>
52#include <functional>
53#endif
54
55#include <gecode/kernel.hh>
56
57/*
58 * Configure linking
59 *
60 */
61#if !defined(GECODE_STATIC_LIBS) && \
62 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
63
64#ifdef GECODE_BUILD_SEARCH
65#define GECODE_SEARCH_EXPORT __declspec( dllexport )
66#else
67#define GECODE_SEARCH_EXPORT __declspec( dllimport )
68#endif
69
70#else
71
72#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
73#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
74#else
75#define GECODE_SEARCH_EXPORT
76#endif
77
78#endif
79
80// Configure auto-linking
81#ifndef GECODE_BUILD_SEARCH
82#define GECODE_LIBRARY_NAME "Search"
84#endif
85
86
87namespace Gecode { namespace Search {
88
90 namespace Sequential {}
91
93 namespace Parallel {}
94
96 namespace Meta {}
97
98 namespace Meta {
99
101 namespace Sequential {}
102
104 namespace Parallel {}
105
106 }
107
108
114 namespace Config {
116 const bool clone = true;
118 const double threads = 1.0;
119
121 const unsigned int c_d = 8;
123 const unsigned int a_d = 2;
124
126 const unsigned int steal_limit = 3;
128 const unsigned int initial_delay = 5;
129
131 const unsigned int d_l = 5;
132
134 const double base = 1.5;
136 const unsigned int slice = 250;
137
139 const unsigned int nogoods_limit = 128;
140
142 const unsigned int cpprofiler_port = 6565U;
143 }
144
145}}
146
148
149namespace Gecode { namespace Search {
150
156 public:
158 unsigned long long int fail;
160 unsigned long long int node;
162 unsigned long int depth;
164 unsigned long int restart;
166 unsigned long int nogood;
168 Statistics(void);
170 void reset(void);
175 };
176
177}}
178
180
181namespace Gecode { namespace Search {
182
183 class WrapTraceRecorder;
184 class TraceRecorder;
185 class EdgeTraceRecorder;
186
187}}
188
189#include <string>
190#include <sstream>
191
192namespace Gecode {
193
199 public:
202 DFS = 0,
203 BAB = 1,
204 LDS = 2,
205 RBS = 3,
206 PBS = 4,
207 AOE = 5
208 };
209
211 protected:
215 unsigned int _fst;
217 unsigned int _lst;
218 public:
220 EngineInfo(void);
222 EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
224
225
226 EngineType type(void) const;
228 bool meta(void) const;
230
232
233 unsigned int wfst(void) const;
235 unsigned int wlst(void) const;
237 unsigned int workers(void) const;
239
241
242 unsigned int efst(void) const;
244 unsigned int elst(void) const;
246 unsigned int engines(void) const;
248 };
249
250 class EdgeInfo {
251 protected:
253 unsigned int _wid;
255 unsigned int _nid;
257 unsigned int _a;
259 std::string _s;
260 public:
262 void init(unsigned int wid, unsigned int nid, unsigned int a);
264 void init(unsigned int wid, unsigned int nid, unsigned int a,
265 const Space& s, const Choice & c);
267 void invalidate(void);
269 EdgeInfo(void);
271 EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
273 operator bool(void) const;
275 unsigned int wid(void) const;
277 unsigned int nid(void) const;
279 unsigned int alternative(void) const;
281 std::string string(void) const;
282 };
283
284 enum NodeType {
285 SOLVED = 0,
286 FAILED = 1,
288 };
289
290 class NodeInfo {
291 protected:
295 unsigned int _wid;
297 unsigned int _nid;
299 const Space& _s;
301 const Choice* _c;
302 public:
305 unsigned int wid, unsigned int nid,
306 const Space& s, const Choice* c = nullptr);
308 NodeType type(void) const;
310 unsigned int wid(void) const;
312 unsigned int nid(void) const;
314 const Space& space(void) const;
316 const Choice& choice(void) const;
317 };
318 private:
322 unsigned int pending;
324 unsigned int n_e;
326 unsigned int n_w;
328 unsigned int n_active;
334 void engine(EngineType t, unsigned int n);
336 void worker(unsigned int& wid, unsigned int& eid);
338 void worker(void);
340 //{@
342 void _round(unsigned int eid);
344 void _skip(const EdgeInfo& ei);
346 void _node(const EdgeInfo& ei, const NodeInfo& ni);
348 public:
350 SearchTracer(void);
352
353
354 unsigned int workers(void) const;
356 unsigned int engines(void) const;
358 const EngineInfo& engine(unsigned int eid) const;
360 unsigned int eid(unsigned int wid) const;
362
364
365 virtual void init(void) = 0;
367 virtual void round(unsigned int eid) = 0;
369 virtual void skip(const EdgeInfo& ei) = 0;
371 virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
373 virtual void done(void) = 0;
375
376 virtual ~SearchTracer(void);
377 };
378
380 protected:
382 std::ostream& os;
384 static const char* t2s[EngineType::AOE + 1];
385 public:
387 StdSearchTracer(std::ostream& os = std::cerr);
389 virtual void init(void);
391 virtual void round(unsigned int eid);
393 virtual void skip(const EdgeInfo& ei);
395 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
397 virtual void done(void);
399 virtual ~StdSearchTracer(void);
402 };
403
404}
405
408
409#ifdef GECODE_HAS_CPPROFILER
410
411namespace Gecode {
412
414 namespace CPProfiler {}
415
416}
417
418namespace Gecode { namespace CPProfiler {
419
421 class Connector;
422
423}}
424
425namespace Gecode {
426
429 public:
432 public:
434 GetInfo(void);
436 virtual std::string getInfo(const Space& home) const = 0;
438 virtual ~GetInfo(void);
439 };
440 private:
442 CPProfiler::Connector* connector;
444 int execution_id;
446 std::string name;
448 int restart;
450 const GetInfo* pgi;
451 public:
453 CPProfilerSearchTracer(int eid, std::string name,
454 unsigned int port = Search::Config::cpprofiler_port,
455 const GetInfo* pgi = nullptr);
457 virtual void init(void);
459 virtual void round(unsigned int eid);
461 virtual void skip(const EdgeInfo& ei);
463 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
465 virtual void done(void);
468 };
469
470}
471
472#endif
473
474namespace Gecode { namespace Search {
475
481 public:
483
484
485 Cutoff(void);
487 virtual unsigned long long int operator ()(void) const = 0;
489 virtual unsigned long long int operator ++(void) = 0;
491 virtual ~Cutoff(void);
493
495
496 static Cutoff*
497 constant(unsigned long long int scale=Config::slice);
499 static Cutoff*
500 linear(unsigned long long int scale=Config::slice);
504 static Cutoff*
505 geometric(unsigned long long int scale=Config::slice,
506 double base=Config::base);
508 static Cutoff*
509 luby(unsigned long long int scale=Config::slice);
514 static Cutoff*
515 rnd(unsigned int seed,
516 unsigned long long int min, unsigned long long int max,
517 unsigned long long int n);
519 static Cutoff*
520 append(Cutoff* c1, unsigned long long int n, Cutoff* c2);
522 static Cutoff*
523 merge(Cutoff* c1, Cutoff* c2);
525 static Cutoff*
526 repeat(Cutoff* c, unsigned long long int n);
528 };
529
535 protected:
537 unsigned long long int c;
538 public:
540 CutoffConstant(unsigned long long int c);
542 virtual unsigned long long int operator ()(void) const;
544 virtual unsigned long long int operator ++(void);
545 };
546
552 protected:
554 unsigned long long int scale;
556 unsigned long long int n;
557 public:
559 CutoffLinear(unsigned long long int scale);
561 virtual unsigned long long int operator ()(void) const;
563 virtual unsigned long long int operator ++(void);
564 };
565
571 protected:
573 unsigned long long int i;
575 unsigned long long int scale;
577 static const unsigned long long int n_start = 63U;
579 static unsigned long int start[n_start];
581 static unsigned long long int log(unsigned long long int i);
583 static unsigned long long int luby(unsigned long long int i);
584 public:
586 CutoffLuby(unsigned long long int scale);
588 virtual unsigned long long int operator ()(void) const;
590 virtual unsigned long long int operator ++(void);
591 };
592
598 protected:
600 double n;
602 double scale;
604 double base;
605 public:
607 CutoffGeometric(unsigned long long int scale, double base);
609 virtual unsigned long long int operator ()(void) const;
611 virtual unsigned long long int operator ++(void);
612 };
613
619 protected:
623 unsigned long long int min;
625 unsigned long long int n;
627 unsigned long long int step;
629 unsigned long long int cur;
630 public:
632 CutoffRandom(unsigned int seed,
633 unsigned long long int min, unsigned long long int max,
634 unsigned long long int n);
636 virtual unsigned long long int operator ()(void) const;
638 virtual unsigned long long int operator ++(void);
639 };
640
646 protected:
652 unsigned long long int n;
653 public:
655 CutoffAppend(Cutoff* c1, unsigned long long int n, Cutoff* c2);
657 virtual unsigned long long int operator ()(void) const;
659 virtual unsigned long long int operator ++(void);
661 virtual ~CutoffAppend(void);
662 };
663
669 protected:
674 public:
678 virtual unsigned long long int operator ()(void) const;
680 virtual unsigned long long int operator ++(void);
682 virtual ~CutoffMerge(void);
683 };
684
690 protected:
693 // Current cutoff
694 unsigned long long int cutoff;
695 // Iteration
696 unsigned long long int i;
697 // Number of repetitions
698 unsigned long long int n;
699 public:
701 CutoffRepeat(Cutoff* c, unsigned long long int n);
703 virtual unsigned long long int operator ()(void) const;
705 virtual unsigned long long int operator ++(void);
707 virtual ~CutoffRepeat(void);
708 };
709
710}}
711
713
714namespace Gecode { namespace Search {
715
716 class WorkerControlAccess;
717
774 private:
775 class State;
776 State* state;
778 public:
780 WorkerControl(void) noexcept;
782 explicit WorkerControl(unsigned int requested);
786 WorkerControl& operator =(const WorkerControl& control);
790 bool engaged(void) const noexcept;
792 unsigned int requested(void) const noexcept;
801 void request(unsigned int workers);
803 unsigned int capacity(void) const noexcept;
804 };
805
806 class Stop;
807#ifdef GECODE_HAS_EXPERIMENTAL
808 class HeuristicGuidance;
809#endif
810
848 class Options {
849 public:
851 bool clone;
853 double threads;
863 unsigned int c_d;
865 unsigned int a_d;
867 unsigned int d_l;
869 unsigned int assets;
871 unsigned int slice;
873 unsigned int nogoods_limit;
880#ifdef GECODE_HAS_EXPERIMENTAL
884 unsigned long int max_width;
886 unsigned long int frontier_limit;
887#endif
891 Options(void);
894 expand(void) const;
895 };
896
897}}
898
900
902
903namespace Gecode { namespace Search {
904
914
920 public:
922
923
924 Stop(void);
926 virtual bool stop(const Statistics& s, const Options& o) = 0;
928 virtual ~Stop(void);
930
932
933 static Stop* node(unsigned long long int l);
935 static Stop* fail(unsigned long long int l);
937 static Stop* time(double l);
939 static Stop* restart(unsigned long long int l);
941 };
942
952 protected:
954 std::atomic<unsigned long long int> l;
955 public:
957 NodeStop(unsigned long long int l);
959 NodeStop(const NodeStop& s);
961 NodeStop& operator =(const NodeStop& s);
963 unsigned long long int limit(void) const;
965 void limit(unsigned long long int l);
967 virtual bool stop(const Statistics& s, const Options& o);
968 };
969
979 protected:
981 std::atomic<unsigned long long int> l;
982 public:
984 FailStop(unsigned long long int l);
986 FailStop(const FailStop& s);
988 FailStop& operator =(const FailStop& s);
990 unsigned long long int limit(void) const;
992 void limit(unsigned long long int l);
994 virtual bool stop(const Statistics& s, const Options& o);
995 };
996
1007 protected:
1008 using clock = std::chrono::steady_clock;
1009 using clock_rep = clock::time_point::rep;
1011 std::atomic<clock_rep> t0;
1013 std::atomic<double> l;
1014 public:
1016 TimeStop(double l);
1018 TimeStop(const TimeStop& s);
1020 TimeStop& operator =(const TimeStop& s);
1022 double limit(void) const;
1024 void limit(double l);
1026 void reset(void);
1028 virtual bool stop(const Statistics& s, const Options& o);
1029 };
1030
1036 protected:
1038 std::atomic<unsigned long long int> l;
1039 public:
1041 RestartStop(unsigned long long int l);
1043 RestartStop(const RestartStop& s);
1045 RestartStop& operator =(const RestartStop& s);
1047 unsigned long long int limit(void) const;
1049 void limit(unsigned long long int l);
1051 virtual bool stop(const Statistics& s, const Options& o);
1052 };
1053
1054}}
1055
1056#include <gecode/search/stop.hpp>
1057
1058namespace Gecode { namespace Search {
1059
1064 protected:
1068 Engine(void);
1070 Engine(const Options& o, unsigned int capacity);
1071 public:
1073 virtual Space* next(void) = 0;
1075 virtual Statistics statistics(void) const = 0;
1077 virtual bool stopped(void) const = 0;
1078#ifdef GECODE_HAS_EXPERIMENTAL
1080 virtual bool limited(void) const;
1081#endif
1083 virtual void constrain(const Space& b);
1085 virtual void reset(Space* s);
1087 virtual NoGoods& nogoods(void);
1089 virtual ~Engine(void);
1090 };
1091
1092}}
1093
1094#include <gecode/search/engine.hpp>
1095
1096namespace Gecode { namespace Search {
1097
1099 template<class T>
1100 class Base : public HeapAllocated {
1101 template<class, class>
1102 friend Engine* build(Space*, const Options&);
1103 template<class, template<class> class>
1104 friend Engine* build(Space*, const Options&);
1105 protected:
1109 Base(Engine* e = nullptr);
1110 public:
1112 virtual T* next(void);
1114 virtual Statistics statistics(void) const;
1116 virtual bool stopped(void) const;
1118 virtual ~Base(void);
1119 private:
1121 Base(const Base&);
1123 Base& operator =(const Base&);
1124 };
1125
1126}}
1127
1128#include <gecode/search/base.hpp>
1129
1130namespace Gecode { namespace Search {
1131
1133 template<class T, class E>
1134 Engine* build(Space* s, const Options& opt);
1136 template<class T, template<class> class E>
1137 Engine* build(Space* s, const Options& opt);
1138
1141 protected:
1145 const bool b;
1146 public:
1148 Builder(const Options& opt, bool best);
1150 Options& options(void);
1152 const Options& options(void) const;
1154 bool best(void) const;
1156 virtual Engine* operator() (Space* s) const = 0;
1158 virtual ~Builder(void);
1159 };
1160
1161}}
1162
1163#include <gecode/search/build.hpp>
1164
1165namespace Gecode {
1166
1169
1170}
1171
1172#include <gecode/search/traits.hpp>
1173
1174namespace Gecode {
1175
1177 class SEBs : public ArgArray<SEB> {
1178 public:
1180
1181
1182 SEBs(void);
1184 explicit SEBs(int n);
1186 SEBs(const std::vector<SEB>& x);
1188 SEBs(std::initializer_list<SEB> x);
1190 template<class InputIterator>
1191 SEBs(InputIterator first, InputIterator last);
1193 SEBs(const ArgArray<SEB>& a);
1195 };
1196
1197}
1198
1199#include <gecode/search/sebs.hpp>
1200
1201namespace Gecode {
1202
1210 template<class T>
1211 class DFS : public Search::Base<T> {
1212 public:
1216 static const bool best = false;
1217 };
1218
1220 template<class T>
1221 T* dfs(T* s, const Search::Options& o=Search::Options::def);
1222
1224 template<class T>
1226
1227}
1228
1229#include <gecode/search/dfs.hpp>
1230
1231#ifdef GECODE_HAS_EXPERIMENTAL
1232namespace Gecode { namespace Search {
1233
1260 public:
1264 typedef std::function<std::int64_t(const Space&)> Evaluate;
1272 std::function<bool(const Space&,const Space&)> dominates;
1274 std::function<std::size_t(const Space&)> dominance_key;
1277 : sense(s), bound(std::move(b)), rank(std::move(r)) {}
1278 };
1279
1280}}
1281
1282namespace Gecode {
1283
1296 template<class T>
1297 class AStar : public Search::Base<T> {
1298 public:
1302 static const bool best = true;
1303 };
1304
1306 template<class T>
1307 T* astar(T* s, const Search::Options& o=Search::Options::def);
1308
1310 template<class T>
1312
1313}
1314
1315#include <gecode/search/astar.hpp>
1316
1317namespace Gecode {
1318
1336 template<class T>
1337 class CABS : public Search::Base<T> {
1338 public:
1342 static const bool best = true;
1343 };
1344
1346 template<class T>
1347 T* cabs(T* s, const Search::Options& o=Search::Options::def);
1348
1350 template<class T>
1352
1353}
1354
1355#include <gecode/search/cabs.hpp>
1356
1357#endif
1358
1359namespace Gecode {
1360
1372 template<class T>
1373 class BAB : public Search::Base<T> {
1374 public:
1378 static const bool best = true;
1379 };
1380
1393 template<class T>
1394 T* bab(T* s, const Search::Options& o=Search::Options::def);
1395
1397 template<class T>
1399
1400}
1401
1402#include <gecode/search/bab.hpp>
1403
1404namespace Gecode {
1405
1410 template<class T>
1411 class LDS : public Search::Base<T> {
1412 public:
1416 static const bool best = false;
1417 };
1418
1423 template<class T>
1424 T* lds(T* s, const Search::Options& o=Search::Options::def);
1425
1427 template<class T>
1429
1430}
1431
1432#include <gecode/search/lds.hpp>
1433
1434namespace Gecode {
1435
1454 template<class T, template<class> class E = DFS>
1455 class RBS : public Search::Base<T> {
1456 using Search::Base<T>::e;
1457 public:
1459 RBS(T* s, const Search::Options& o);
1461 static const bool best = E<T>::best;
1462 };
1463
1482 template<class T, template<class> class E>
1483 T* rbs(T* s, const Search::Options& o);
1484
1486 template<class T, template<class> class E>
1487 SEB rbs(const Search::Options& o);
1488
1489}
1490
1491#include <gecode/search/rbs.hpp>
1492
1493namespace Gecode { namespace Search { namespace Meta {
1494
1496 template<class T, template<class> class E>
1497 Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
1498
1500 template<class T, template<class> class E>
1501 Engine* sequential(T* master, SEBs& sebs,
1502 const Search::Statistics& stat, Options& opt, bool best);
1503
1504#ifdef GECODE_HAS_THREADS
1505
1507 template<class T, template<class> class E>
1508 Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
1509
1511 template<class T, template<class> class E>
1512 Engine* parallel(T* master, SEBs& sebs,
1513 const Search::Statistics& stat, Options& opt, bool best);
1514
1515#endif
1516
1517}}}
1518
1519namespace Gecode {
1520
1542 template<class T, template<class> class E = DFS>
1543 class PBS : public Search::Base<T> {
1544 using Search::Base<T>::e;
1545 protected:
1547 void build(T* s, SEBs& sebs, const Search::Options& o);
1548 public:
1562 PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
1564 void constrain(const T& b);
1566 static const bool best = E<T>::best;
1567 };
1568
1588 template<class T, template<class> class E>
1589 T* pbs(T* s, const Search::Options& o=Search::Options::def);
1590
1592 template<class T>
1594
1595}
1596
1597#include <gecode/search/pbs.hpp>
1598
1599#endif
1600
1601// STATISTICS: search-other
AStar(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition astar.hpp:69
static const bool best
Whether engine does best solution search.
Definition search.hh:1302
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:1378
static const bool best
Whether engine does best solution search.
Definition search.hh:1342
CABS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition cabs.hpp:69
Class to send solution information to CPProfiler.
Definition search.hh:431
virtual std::string getInfo(const Space &home) const =0
Return info for a space.
virtual void done(void)
All workers are done.
virtual ~CPProfilerSearchTracer(void)
Delete.
virtual void round(unsigned int eid)
The engine with id eid goes to a next round (restart or next iteration in LDS).
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
virtual void init(void)
The search engine initializes.
CPProfilerSearchTracer(int eid, std::string name, unsigned int port=Search::Config::cpprofiler_port, const GetInfo *pgi=nullptr)
Initialize.
Choice for performing commit
Definition core.hpp:1430
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:1216
Base class for heap allocated objects.
Definition heap.hpp:344
static const bool best
Whether engine does best solution search.
Definition search.hh:1416
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:1606
void constrain(const T &b)
Constrain future portfolio solutions to be better than b.
Definition pbs.hpp:442
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition pbs.hpp:392
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition pbs.hpp:347
static const bool best
Whether engine does best solution search.
Definition search.hh:1566
static const bool best
Whether engine does best solution search.
Definition search.hh:1461
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition rbs.hpp:84
Passing search engine builder arguments.
Definition search.hh:1177
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
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int _a
Number of alternative.
Definition search.hh:257
unsigned int _nid
The parent node id.
Definition search.hh:255
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:253
std::string _s
String corresponding to alternative.
Definition search.hh:259
Information about an engine.
Definition search.hh:210
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:217
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:213
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:215
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:295
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH).
Definition search.hh:301
NodeType _nt
The node type.
Definition search.hh:293
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:297
const Space & _s
The corresponding space.
Definition search.hh:299
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:195
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:284
@ FAILED
A solution node.
Definition search.hh:286
@ BRANCH
A failed node.
Definition search.hh:287
virtual void init(void)=0
The search engine initializes.
EngineType
Which type of engine.
Definition search.hh:201
@ BAB
Engine is a BAB engine.
Definition search.hh:203
@ DFS
Engine is a DFS engine.
Definition search.hh:202
@ AOE
Unspecified engine (any other engine).
Definition search.hh:207
@ PBS
Engine is a PBS engine.
Definition search.hh:206
@ RBS
Engine is a RBS engine.
Definition search.hh:205
@ LDS
Engine is a LDS engine.
Definition search.hh:204
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:266
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:1100
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition base.hpp:56
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
virtual Statistics statistics(void) const
Return statistics.
Definition base.hpp:51
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Definition build.hpp:55
Base(Engine *e=nullptr)
Constructor.
Definition base.hpp:42
Engine * e
The actual search engine.
Definition search.hh:1107
A class for building search engines.
Definition search.hh:1140
virtual ~Builder(void)
Destructor.
const bool b
Whether engine to be built is a best solution search engine.
Definition search.hh:1145
Options opt
Stored and already expanded options.
Definition search.hh:1143
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 long int n
How many number to take from the first.
Definition search.hh:652
CutoffAppend(Cutoff *c1, unsigned long long int n, Cutoff *c2)
Constructor.
Definition cutoff.hpp:100
Cutoff * c1
First cutoff generators.
Definition search.hh:648
Cutoff * c2
Second cutoff generators.
Definition search.hh:650
CutoffConstant(unsigned long long int c)
Constructor.
Definition cutoff.hpp:47
unsigned long long int c
Constant.
Definition search.hh:537
double n
Current cutoff value.
Definition search.hh:600
CutoffGeometric(unsigned long long int scale, double base)
Constructor.
Definition cutoff.hpp:83
double scale
Scale factor.
Definition search.hh:602
unsigned long long int n
Next number in sequence.
Definition search.hh:556
CutoffLinear(unsigned long long int scale)
Constructor.
Definition cutoff.hpp:52
unsigned long long int scale
Scale factor.
Definition search.hh:554
static const unsigned long long int n_start
Number of pre-computed luby values.
Definition search.hh:577
unsigned long long int i
Iteration number.
Definition search.hh:573
static unsigned long long int log(unsigned long long int i)
Compute binary logarithm of i.
Definition cutoff.hpp:60
CutoffLuby(unsigned long long int scale)
Constructor.
Definition cutoff.hpp:57
static unsigned long int start[n_start]
Precomputed luby-values.
Definition search.hh:579
unsigned long long int scale
Scale factor.
Definition search.hh:575
static unsigned long long int luby(unsigned long long int i)
Compute Luby number for step i.
Definition cutoff.hpp:68
Cutoff * c1
First cutoff generator.
Definition search.hh:671
Cutoff * c2
Second cutoff generator.
Definition search.hh:673
CutoffMerge(Cutoff *c1, Cutoff *c2)
Constructor.
Definition cutoff.hpp:109
CutoffRandom(unsigned int seed, unsigned long long int min, unsigned long long int max, unsigned long long int n)
Constructor.
Definition cutoff.hpp:88
unsigned long long int n
Random values.
Definition search.hh:625
unsigned long long int step
Step size.
Definition search.hh:627
unsigned long long int cur
Current value.
Definition search.hh:629
unsigned long long int min
Minimum cutoff value.
Definition search.hh:623
Support::RandomGenerator rnd
Random number generator.
Definition search.hh:621
Cutoff * c
Actual cutoff generator.
Definition search.hh:692
unsigned long long int n
Definition search.hh:698
unsigned long long int cutoff
Definition search.hh:694
CutoffRepeat(Cutoff *c, unsigned long long int n)
Constructor.
Definition cutoff.hpp:118
unsigned long long int i
Definition search.hh:696
Base class for cutoff generators for restart-based meta engine.
Definition search.hh:480
static Cutoff * linear(unsigned long long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
static Cutoff * append(Cutoff *c1, unsigned long long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
static Cutoff * rnd(unsigned int seed, unsigned long long int min, unsigned long long int max, unsigned long long int n)
Cutoff(void)
Default constructor.
Definition cutoff.hpp:41
static Cutoff * repeat(Cutoff *c, unsigned long long int n)
Create generator that repeats n times each cutoff value from c.
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
static Cutoff * constant(unsigned long long int scale=Config::slice)
Create generator for constant sequence with constant s.
static Cutoff * luby(unsigned long long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Recorder for a search tracer with edge information.
Search engine implementation interface
Definition search.hh:1063
Engine(void)
Construct a meta engine without worker control.
Engine(const Options &o, unsigned int capacity)
Construct a leaf engine and bind worker control to capacity.
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception).
virtual bool limited(void) const
Whether the engine stopped at a local limit (such as a CABS width limit) and cannot continue.
virtual Statistics statistics(void) const =0
Return statistics.
virtual Space * next(void)=0
Return next solution (nullptr, if none exists or search has been stopped).
virtual void reset(Space *s)
Reset engine to restart at space s (does nothing).
virtual bool stopped(void) const =0
Check whether engine has been stopped.
virtual ~Engine(void)
Destructor.
virtual NoGoods & nogoods(void)
Return no-goods (the no-goods are empty).
WorkerControl worker_control
Control retained for the lifetime of a leaf engine.
Definition search.hh:1066
std::atomic< unsigned long long int > l
Failure limit.
Definition search.hh:981
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
FailStop(unsigned long long int l)
Stop if failure limit l is exceeded.
Definition stop.hpp:83
unsigned long long int limit(void) const
Return current limit.
Definition stop.hpp:94
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
Sense
Objective direction.
Definition search.hh:1262
std::function< std::int64_t(const Space &)> Evaluate
Function evaluating a stable space.
Definition search.hh:1264
HeuristicGuidance(Sense s, Evaluate b, Evaluate r=Evaluate())
Initialize guidance.
Definition search.hh:1276
Sense sense
Objective direction.
Definition search.hh:1266
Evaluate rank
Node rank (optional, lower first).
Definition search.hh:1270
std::function< bool(const Space &, const Space &)> dominates
Whether the first space dominates the second (optional).
Definition search.hh:1272
std::function< std::size_t(const Space &)> dominance_key
Dominance key (optional).
Definition search.hh:1274
Evaluate bound
Optimistic objective bound (required).
Definition search.hh:1268
NodeStop(unsigned long long int l)
Stop if node limit l is exceeded.
Definition stop.hpp:56
unsigned long long int limit(void) const
Return current limit.
Definition stop.hpp:67
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
std::atomic< unsigned long long int > l
Node limit.
Definition search.hh:954
Search engine options
Definition search.hh:848
static const Options def
Default options.
Definition search.hh:889
unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:863
unsigned long int frontier_limit
Maximal number of stored nodes for CABS (zero for no limit).
Definition search.hh:886
WorkerControl worker_control
Definition search.hh:861
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:851
Options(void)
Initialize with default values.
Definition options.hpp:37
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Definition search.hh:882
unsigned int d_l
Discrepancy limit (for LDS).
Definition search.hh:867
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:877
Options expand(void) const
Expand with real number of threads.
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:865
Stop * stop
Stop object for stopping search.
Definition search.hh:875
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
unsigned long int max_width
Maximal beam width for CABS (zero for no limit).
Definition search.hh:884
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:869
unsigned int slice
Size of a slice in a portfolio (in number of failures).
Definition search.hh:871
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition search.hh:873
double threads
Number of threads to use.
Definition search.hh:853
std::atomic< unsigned long long int > l
Restart limit.
Definition search.hh:1038
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
RestartStop(unsigned long long int l)
Stop if restart limit l is exceeded.
Definition stop.hpp:149
unsigned long long int limit(void) const
Return current limit.
Definition stop.hpp:160
Search engine statistics
Definition search.hh:155
Statistics(void)
Initialize.
unsigned long int restart
Number of restarts.
Definition search.hh:164
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
unsigned long int depth
Maximum depth of search stack.
Definition search.hh:162
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
Statistics operator+(const Statistics &s)
Return sum with s.
unsigned long int nogood
Number of no-goods posted.
Definition search.hh:166
Base-class for Stop-object.
Definition search.hh:919
static Stop * node(unsigned long long int l)
Stop if node limit l has been exceeded.
Stop(void)
Default constructor.
Definition stop.hpp:45
virtual bool stop(const Statistics &s, const Options &o)=0
Stop search, if returns true.
static Stop * time(double l)
Stop if time limit l (in milliseconds) has been exceeded.
static Stop * fail(unsigned long long int l)
Stop if failure limit l has been exceeded.
static Stop * restart(unsigned long long int l)
Stop if restart limit l has been exceeded.
clock::time_point::rep clock_rep
Definition search.hh:1009
virtual bool stop(const Statistics &s, const Options &o)
Return true if time limit is exceeded.
std::chrono::steady_clock clock
Definition search.hh:1008
TimeStop(double l)
Stop if search exceeds l milliseconds (from creation of this object).
Definition stop.hpp:110
double limit(void) const
Return current limit in milliseconds.
Definition stop.hpp:128
std::atomic< double > l
Current limit in milliseconds.
Definition search.hh:1013
std::atomic< clock_rep > t0
Clock representation at the start of timing.
Definition search.hh:1011
void reset(void)
Reset time to zero.
Definition stop.hpp:138
Simple recorder for a search tracer.
External control for the requested number of search workers.
Definition search.hh:773
~WorkerControl(void)
Destructor.
WorkerControl(unsigned int requested)
Construct an engaged handle with initial request requested (zero pauses).
WorkerControl(void) noexcept
Construct an empty handle.
bool engaged(void) const noexcept
Whether this handle is engaged.
WorkerControl(const WorkerControl &control)
Copy constructor.
friend class WorkerControlAccess
Definition search.hh:777
unsigned int requested(void) const noexcept
Return the requested number of workers (zero also denotes an empty handle).
void request(unsigned int workers)
Request workers workers (zero pauses the engine).
unsigned int capacity(void) const noexcept
Return the fixed worker capacity, or zero before attachment.
Recorder for engine events (for access control).
Computation spaces.
Definition core.hpp:1782
StatusStatistics(void)
Initialize.
Definition core.hpp:4968
virtual void init(void)
The search engine initializes.
StdSearchTracer(std::ostream &os=std::cerr)
Initialize with output stream os.
virtual ~StdSearchTracer(void)
Delete.
virtual void round(unsigned int eid)
The engine with id eid goes to a next round (restart or next iteration in LDS).
virtual void done(void)
All workers are done.
static StdSearchTracer def
Default tracer (printing to std::cerr).
Definition search.hh:401
static const char * t2s[EngineType::AOE+1]
Map engine type to string.
Definition search.hh:384
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
std::ostream & os
Output stream to use.
Definition search.hh:382
Array with arbitrary number of elements.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:78
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:448
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:120
Code that is specific to the CPProfiler.
Definition search.hh:414
Search configuration
Definition search.hh:114
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:128
const unsigned int d_l
Default discrepancy limit for LDS.
Definition search.hh:131
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:123
const double base
Base for geometric restart sequence.
Definition search.hh:134
const unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:121
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures).
Definition search.hh:136
const unsigned int cpprofiler_port
Default port for CPProfiler.
Definition search.hh:142
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition search.hh:139
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition search.hh:126
const double threads
Number of threads to use.
Definition search.hh:118
const bool clone
Whether engines create a clone when being initialized.
Definition search.hh:116
Parallel meta search engine implementations
Definition search.hh:104
Sequential meta search engine implementations
Definition search.hh:101
Meta search engine implementations
Definition search.hh:96
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:93
Sequential search engine implementations
Definition search.hh:90
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition build.hpp:55
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
Definition search.hh:1168
T * astar(T *s, const Search::Options &o=Search::Options::def)
Perform A* search for subclass T of space s and options o.
Definition astar.hpp:74
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
T * cabs(T *s, const Search::Options &o=Search::Options::def)
Perform CABS search for subclass T of space s and options o.
Definition cabs.hpp:74
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 .
#define GECODE_SEARCH_EXPORT
Definition search.hh:75
const int capacity[n_warehouses]
Capacity of a single warehouse.