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"
79namespace Gecode {
namespace Search {
113 const unsigned int c_d = 8;
115 const unsigned int a_d = 2;
123 const unsigned int d_l = 5;
141namespace Gecode {
namespace Search {
173namespace Gecode {
namespace Search {
175 class WrapTraceRecorder;
177 class EdgeTraceRecorder;
220 bool meta(
void)
const;
225 unsigned int wfst(
void)
const;
227 unsigned int wlst(
void)
const;
229 unsigned int workers(
void)
const;
234 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);
346 unsigned int workers(
void)
const;
348 unsigned int engines(
void)
const;
352 unsigned int eid(
unsigned int wid)
const;
381 virtual void init(
void);
383 virtual void round(
unsigned int eid);
389 virtual void done(
void);
401#ifdef GECODE_HAS_CPPROFILER
410namespace Gecode {
namespace CPProfiler {
449 virtual void init(
void);
451 virtual void round(
unsigned int eid);
457 virtual void done(
void);
466namespace 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);
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);
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);
705namespace Gecode {
namespace Search {
783namespace Gecode {
namespace Search {
813 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);
894namespace Gecode {
namespace Search {
921namespace Gecode {
namespace Search {
926 template<
class,
class>
928 template<
class,
template<
class>
class>
937 virtual T*
next(
void);
941 virtual bool stopped(
void)
const;
955namespace 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);
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>
1190namespace 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>
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
static const bool best
Whether engine does best solution search.
Class to send solution information to CPProfiler.
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.
virtual void init(void)
The search engine initializes.
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
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.
CPProfilerSearchTracer(int eid, std::string name, unsigned int port=Search::Config::cpprofiler_port, const GetInfo *pgi=nullptr)
Initialize.
Choice for performing commit
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
static const bool best
Whether engine does best solution search.
Base class for heap allocated objects.
static const bool best
Whether engine does best solution search.
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
No-goods recorded from restarts.
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
static const bool best
Whether engine does best solution search.
static const bool best
Whether engine does best solution search.
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Passing search engine builder arguments.
SEBs(void)
Allocate empty array.
void invalidate(void)
Invalidate edge information (for stealing)
unsigned int alternative(void) const
Return number of alternative.
unsigned int _a
Number of alternative.
unsigned int _nid
The parent node id.
unsigned int wid(void) const
Return parent worker id.
std::string string(void) const
Return string for alternative.
unsigned int nid(void) const
Return parent node id.
EdgeInfo(void)
Initialize as non existing.
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
std::string _s
String corresponding to alternative.
Information about an engine.
bool meta(void) const
Return whether engine is a meta engine.
unsigned int wfst(void) const
Return id of first worker.
unsigned int _lst
Last worker or engine.
EngineInfo(void)
Do not initialize.
unsigned int workers(void) const
Return number of workers.
EngineType _type
The engine type.
EngineType type(void) const
Return engine type.
unsigned int efst(void) const
Return id of first engine.
unsigned int engines(void) const
Return number of engines.
unsigned int _fst
First worker or engine.
unsigned int elst(void) const
Return id of last engine.
unsigned int wlst(void) const
Return id of last worker plus one.
unsigned int _wid
The worker id.
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
NodeType _nt
The node type.
NodeType type(void) const
Return node type.
const Choice & choice(void) const
Return corresponding choice.
unsigned int nid(void) const
Return node id.
unsigned int wid(void) const
Return worker id.
const Space & space(void) const
Return corresponding space.
unsigned int _nid
The node id.
const Space & _s
The corresponding space.
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Support for tracing search.
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
virtual void init(void)=0
The search engine initializes.
EngineType
Which type of engine.
@ BAB
Engine is a BAB engine.
@ DFS
Engine is a DFS engine.
@ AOE
Unspecified engine (any other engine)
@ PBS
Engine is a PBS engine.
@ RBS
Engine is a RBS engine.
@ LDS
Engine is a LDS engine.
unsigned int engines(void) const
Return number of engines.
virtual ~SearchTracer(void)
Delete.
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.
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
SearchTracer(void)
Initialize.
virtual void done(void)=0
All workers are done.
Base-class for search engines.
Base(Engine *e=NULL)
Constructor.
virtual bool stopped(void) const
Check whether engine has been stopped.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
virtual Statistics statistics(void) const
Return statistics.
virtual ~Base(void)
Destructor.
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Engine * e
The actual search engine.
A class for building search engines.
const bool b
Whether engine to be built is a best solution search engine.
Options opt
Stored and already expanded options.
Builder(const Options &opt, bool best)
Initialize with options opt and best solution search support.
bool best(void) const
Whether engine is a best solution search engine.
Options & options(void)
Provide access to options.
unsigned long int n
How many number to take from the first.
Cutoff * c1
First cutoff generators.
Cutoff * c2
Second cutoff generators.
CutoffAppend(Cutoff *c1, unsigned long int n, Cutoff *c2)
Constructor.
unsigned long int c
Constant.
CutoffConstant(unsigned long int c)
Constructor.
double n
Current cutoff value.
CutoffGeometric(unsigned long int scale, double base)
Constructor.
double scale
Scale factor.
unsigned long int n
Next number in sequence.
CutoffLinear(unsigned long int scale)
Constructor.
unsigned long int scale
Scale factor.
static unsigned long int luby(unsigned long int i)
Compute Luby number for step i.
static const unsigned long int n_start
Number of pre-computed luby values.
CutoffLuby(unsigned long int scale)
Constructor.
static unsigned long int log(unsigned long int i)
Compute binary logarithm of i.
unsigned long int scale
Scale factor.
unsigned long int i
Iteration number.
static unsigned long int start[n_start]
Precomputed luby-values.
Cutoff * c1
First cutoff generator.
Cutoff * c2
Second cutoff generator.
CutoffMerge(Cutoff *c1, Cutoff *c2)
Constructor.
unsigned long int step
Step size.
unsigned long int cur
Current value.
CutoffRandom(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Constructor.
unsigned long int n
Random values.
Support::RandomGenerator rnd
Random number generator.
unsigned long int min
Minimum cutoff value.
CutoffRepeat(Cutoff *c, unsigned long int n)
Constructor.
Cutoff * c
Actual cutoff generator.
Base class for cutoff generators for restart-based meta engine.
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
static Cutoff * linear(unsigned long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Cutoff(void)
Default constructor.
static Cutoff * luby(unsigned long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
static Cutoff * append(Cutoff *c1, unsigned long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Recorder for a search tracer with edge information.
Search engine implementation interface
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception)
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)
virtual bool stopped(void) const =0
Check whether engine has been stopped.
virtual NoGoods & nogoods(void)
Return no-goods (the no-goods are empty)
unsigned long int l
Failure limit.
FailStop(unsigned long int l)
Stop if failure limit l is exceeded.
unsigned long int limit(void) const
Return current limit.
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
unsigned long int limit(void) const
Return current limit.
NodeStop(unsigned long int l)
Stop if node limit l is exceeded.
unsigned long int l
Node limit.
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
static const Options def
Default options.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
bool clone
Whether engines create a clone when being initialized.
Options(void)
Initialize with default values.
unsigned int d_l
Discrepancy limit (for LDS)
Cutoff * cutoff
Cutoff for restart-based search.
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)
Stop * stop
Stop object for stopping search.
SearchTracer * tracer
Tracer object for tracing search.
unsigned int assets
Number of assets (engines) in a portfolio.
unsigned int slice
Size of a slice in a portfolio (in number of failures)
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
double threads
Number of threads to use.
Statistics(void)
Initialize.
unsigned long int restart
Number of restarts.
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
unsigned long int depth
Maximum depth of search stack.
unsigned long int fail
Number of failed nodes in search tree.
unsigned long int node
Number of nodes expanded.
Statistics operator+(const Statistics &s)
Return sum with s.
unsigned long int nogood
Number of no-goods posted.
Base-class for Stop-object.
Stop(void)
Default constructor.
static Stop * node(unsigned long int l)
Stop if node limit l has been exceeded.
static Stop * time(unsigned long int l)
Stop if time limit l (in milliseconds) has been exceeded.
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.
virtual bool stop(const Statistics &s, const Options &o)
Return true if time limit is exceeded.
unsigned long int limit(void) const
Return current limit in milliseconds.
TimeStop(unsigned long int l)
Stop if search exceeds l milliseconds (from creation of this object)
Support::Timer t
Time when execution should stop.
unsigned long int l
Current limit in milliseconds.
void reset(void)
Reset time to zero.
Simple recorder for a search tracer.
Recorder for engine events (for access control)
StatusStatistics(void)
Initialize.
static const char * t2s[EngineType::AOE+1]
Map engine type to string.
StdSearchTracer(std::ostream &os=std::cerr)
Initialize with output stream os.
virtual void done(void)
All workers are done.
virtual void init(void)
The search engine initializes.
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
static StdSearchTracer def
Default tracer (printing to std::cerr)
virtual void round(unsigned int eid)
The engine with id eid goes to a next round (restart or next iteration in LDS)
std::ostream & os
Output stream to use.
virtual void skip(const EdgeInfo &ei)
The engine skips an edge.
Array with arbitrary number of elements.
A mutex for mutual exclausion among several threads.
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
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.
T * lds(T *s, const Search::Options &o=Search::Options::def)
Invoke limited-discrepancy search for s as root node and optionso.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Code that is specific to the CPProfiler.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
const unsigned int d_l
Default discrepancy limit for LDS.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
const double base
Base for geometric restart sequence.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
const unsigned int cpprofiler_port
Default port for CPProfiler.
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
const double threads
Number of threads to use.
const bool clone
Whether engines create a clone when being initialized.
Parallel search engine implementations
Sequential search engine implementations
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
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.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
#define GECODE_SEARCH_EXPORT