Go to the documentation of this file.
42 #ifndef __GECODE_SEARCH_HH__
43 #define __GECODE_SEARCH_HH__
45 #include <initializer_list>
53 #if !defined(GECODE_STATIC_LIBS) && \
54 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
56 #ifdef GECODE_BUILD_SEARCH
57 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
59 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
64 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
65 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
67 #define GECODE_SEARCH_EXPORT
73 #ifndef GECODE_BUILD_SEARCH
74 #define GECODE_LIBRARY_NAME "Search"
79 namespace Gecode {
namespace Search {
82 namespace Sequential {}
93 namespace Sequential {}
113 const unsigned int c_d = 8;
115 const unsigned int a_d = 2;
123 const unsigned int d_l = 5;
141 namespace Gecode {
namespace Search {
173 namespace Gecode {
namespace Search {
175 class WrapTraceRecorder;
177 class EdgeTraceRecorder;
220 bool meta(
void)
const;
224 unsigned int wfst(
void)
const;
227 unsigned int wlst(
void)
const;
229 unsigned int workers(
void)
const;
233 unsigned int efst(
void)
const;
236 unsigned int elst(
void)
const;
238 unsigned int engines(
void)
const;
254 void init(
unsigned int wid,
unsigned int nid,
unsigned int a);
256 void init(
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;
273 std::string
string(
void)
const;
297 unsigned int wid,
unsigned int nid,
302 unsigned int wid(
void)
const;
304 unsigned int nid(
void)
const;
314 unsigned int pending;
320 unsigned int n_active;
328 void worker(
unsigned int& wid,
unsigned int&
eid);
334 void _round(
unsigned int eid);
345 unsigned int workers(
void)
const;
348 unsigned int engines(
void)
const;
352 unsigned int eid(
unsigned int wid)
const;
356 virtual void init(
void) = 0;
376 static const char* t2s[EngineType::AOE + 1];
381 virtual void init(
void);
383 virtual void round(
unsigned int eid);
385 virtual void skip(
const EdgeInfo& ei);
389 virtual void done(
void);
401 #ifdef GECODE_HAS_CPPROFILER
406 namespace CPProfiler {}
410 namespace Gecode {
namespace CPProfiler {
449 virtual void init(
void);
451 virtual void round(
unsigned int eid);
453 virtual void skip(
const EdgeInfo& ei);
457 virtual void done(
void);
466 namespace Gecode {
namespace Search {
479 virtual unsigned long int operator ()(
void)
const = 0;
481 virtual unsigned long int operator ++(
void) = 0;
506 rnd(
unsigned int seed,
507 unsigned long int min,
unsigned long int max,
508 unsigned long int n);
517 repeat(
Cutoff*
c,
unsigned long int n);
533 virtual unsigned long int operator ()(
void)
const;
535 virtual unsigned long int operator ++(
void);
552 virtual unsigned long int operator ()(
void)
const;
554 virtual unsigned long int operator ++(
void);
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);
579 virtual unsigned long int operator ()(
void)
const;
581 virtual unsigned long int operator ++(
void);
600 virtual unsigned long int operator ()(
void)
const;
602 virtual unsigned long int operator ++(
void);
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);
648 virtual unsigned long int operator ()(
void)
const;
650 virtual unsigned long int operator ++(
void);
669 virtual unsigned long int operator ()(
void)
const;
671 virtual unsigned long int operator ++(
void);
694 virtual unsigned long int operator ()(
void)
const;
696 virtual unsigned long int operator ++(
void);
705 namespace Gecode {
namespace Search {
783 namespace Gecode {
namespace Search {
812 static Stop* node(
unsigned long int l);
815 static Stop* fail(
unsigned long int l);
817 static Stop* time(
unsigned long int l);
837 unsigned long int limit(
void)
const;
839 void limit(
unsigned long int l);
860 unsigned long int limit(
void)
const;
862 void limit(
unsigned long int l);
881 unsigned long int limit(
void)
const;
883 void limit(
unsigned long int l);
894 namespace Gecode {
namespace Search {
908 virtual void constrain(
const Space&
b);
910 virtual void reset(
Space* s);
912 virtual NoGoods& nogoods(
void);
921 namespace Gecode {
namespace Search {
926 template<
class,
class>
928 template<
class,
template<
class>
class>
937 virtual T*
next(
void);
941 virtual bool stopped(
void)
const;
955 namespace Gecode {
namespace Search {
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);
977 const Options& options(
void)
const;
979 bool best(
void)
const;
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);
1151 template<
class T,
template<
class>
class E = DFS>
1158 static const bool best = E<T>::best;
1179 template<
class T,
template<
class>
class E>
1183 template<
class T,
template<
class>
class E>
1190 namespace Gecode {
namespace Search {
namespace Meta {
1193 template<
class T,
template<
class>
class E>
1197 template<
class T,
template<
class>
class E>
1201 #ifdef GECODE_HAS_THREADS
1204 template<
class T,
template<
class>
class E>
1208 template<
class T,
template<
class>
class E>
1235 template<
class T,
template<
class>
class E = DFS>
1247 static const bool best = E<T>::best;
1267 template<
class T,
template<
class>
class E>
SearchTracer(void)
Initialize.
Post propagator for SetVar x
Base(Engine *e=NULL)
Constructor.
const unsigned int cpprofiler_port
Default port for CPProfiler.
unsigned long int n
Next number in sequence.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Cutoff generator for linear sequence.
unsigned int wlst(void) const
Return id of last worker plus one.
unsigned long int l
Node limit.
Support::Timer t
Time when execution should stop.
#define GECODE_SEARCH_EXPORT
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
unsigned long int i
Iteration number.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
unsigned int _wid
The worker id.
A class for building search engines.
unsigned int _fst
First worker or engine.
Depth-first branch-and-bound search engine.
Options(void)
Initialize with default values.
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Base-class for Stop-object.
unsigned long int fail
Number of failed nodes in search tree.
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
static StdSearchTracer def
Default tracer (printing to std::cerr)
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
@ AOE
Unspecified engine (any other engine)
Limited discrepancy search engine.
NodeType type(void) const
Return node type.
double scale
Scale factor.
Array with arbitrary number of elements.
unsigned int nid(void) const
Return parent node id.
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS)
virtual void init(void)=0
The search engine initializes.
const double threads
Number of threads to use.
Cutoff generator that repeats a cutoff from another cutoff generator.
static const bool best
Whether engine does best solution search.
void invalidate(void)
Invalidate edge information (for stealing)
const Space & space(void) const
Return corresponding space.
Depth-first search engine.
Base-class for search engines.
Statistics operator+(const Statistics &s)
Return sum with s.
virtual bool stop(const Statistics &s, const Options &o)=0
Stop search, if returns true.
Simple recorder for a search tracer.
EngineType _type
The engine type.
Recorder for a search tracer with edge information.
virtual void done(void)=0
All workers are done.
SEBs(void)
Allocate empty array.
unsigned int _a
Number of alternative.
unsigned long int depth
Maximum depth of search stack.
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
const bool clone
Whether engines create a clone when being initialized.
unsigned long int l
Current limit in milliseconds.
Stop-object based on time
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
EngineType type(void) const
Return engine type.
unsigned int engines(void) const
Return number of engines.
unsigned int workers(void) const
Return number of workers.
unsigned int alternative(void) const
Return number of alternative.
unsigned int wid(void) const
Return worker id.
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Gecode toplevel namespace
unsigned int _lst
Last worker or engine.
Search::Builder * SEB
Type for a search engine builder.
unsigned long int node
Number of nodes expanded.
Passing search engine builder arguments.
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
T * bab(T *s, const Search::Options &o)
Perform depth-first branch-and-bound search for subclass T of space s and options o.
const Space & _s
The corresponding space.
No-goods recorded from restarts.
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
unsigned int _nid
The parent node id.
Cutoff * c2
Second cutoff generator.
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Cutoff * cutoff
Cutoff for restart-based search.
virtual std::string getInfo(const Space &home) const =0
Return info for a space.
Meta-engine performing restart-based search.
Meta engine using a portfolio of search engines.
Argument array for non-primitive types.
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Stop * stop
Stop object for stopping search.
const unsigned int d_l
Default discrepancy limit for LDS.
unsigned long int step
Step size.
const Choice & choice(void) const
Return corresponding choice.
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
EdgeInfo(void)
Initialize as non existing.
Recorder for engine events (for access control)
unsigned long int n
How many number to take from the first.
Search engine implementation interface
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
unsigned long int l
Failure limit.
Stop-object based on number of nodes
Cutoff * c1
First cutoff generator.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
unsigned long int n
Random values.
double n
Current cutoff value.
unsigned long int scale
Scale factor.
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
unsigned long int c
Constant.
Template for linear congruential generators.
std::string string(void) const
Return string for alternative.
const double base
Base for geometric restart sequence.
unsigned long int cur
Current value.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
unsigned int _nid
The node id.
unsigned int efst(void) const
Return id of first engine.
unsigned int wid(void) const
Return parent worker id.
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Cutoff generator appending two cutoff generators.
Cutoff * c1
First cutoff generators.
Base class for heap allocated objects.
virtual Statistics statistics(void) const =0
Return statistics.
virtual bool stopped(void) const
Check whether engine has been stopped.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Cutoff generator for the Luby sequence.
virtual bool stopped(void) const =0
Check whether engine has been stopped.
NodeType _nt
The node type.
unsigned long int nogood
Number of no-goods posted.
static const bool best
Whether engine does best solution search.
static const bool best
Whether engine does best solution search.
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
Base class for cutoff generators for restart-based meta engine.
Support::RandomGenerator rnd
Random number generator.
Options expand(void) const
Expand with real number of threads.
Cutoff generator merging two cutoff generators.
Class to record search trace info for CPProfiler.
Cutoff generator for the geometric sequence.
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
unsigned int assets
Number of assets (engines) in a portfolio.
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Statistics for execution of status
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
unsigned int nid(void) const
Return node id.
std::ostream & os
Output stream to use.
virtual Statistics statistics(void) const
Return statistics.
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Cutoff generator for constant sequence.
unsigned int elst(void) const
Return id of last engine.
static const bool best
Whether engine does best solution search.
Support for tracing search.
std::string _s
String corresponding to alternative.
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
EngineInfo(void)
Do not initialize.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
virtual ~Base(void)
Destructor.
Stop-object based on number of failures
Options opt
Stored and already expanded options.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
unsigned long int restart
Number of restarts.
static const Options def
Default options.
Gecode::FloatVal c(-8, 8)
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
A mutex for mutual exclausion among several threads.
Information about an engine.
int n
Number of negative literals for node type.
Choice for performing commit
bool clone
Whether engines create a clone when being initialized.
Cutoff * c
Actual cutoff generator.
unsigned int d_l
Discrepancy limit (for LDS)
unsigned int workers(void) const
Return number of workers.
Engine * e
The actual search engine.
Cutoff * c2
Second cutoff generators.
Gecode::IntArgs i({1, 2, 3, 4})
unsigned long int scale
Scale factor.
EngineType
Which type of engine.
unsigned int engines(void) const
Return number of engines.
static const bool best
Whether engine does best solution search.
Cutoff generator for the random sequence.
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Statistics(void)
Initialize.
double threads
Number of threads to use.
bool meta(void) const
Return whether engine is a meta engine.
SearchTracer * tracer
Tracer object for tracing search.
Class to send solution information to CPProfiler.
virtual ~SearchTracer(void)
Delete.
const bool b
Whether engine to be built is a best solution search engine.
unsigned int wfst(void) const
Return id of first worker.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
unsigned long int min
Minimum cutoff value.