search.hh
Go to the documentation of this file.
AStar(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition astar.hpp:69
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition bab.hpp:72
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 node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
Definition tracer.cpp:101
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:73
CPProfilerSearchTracer(int eid, std::string name, unsigned int port=Search::Config::cpprofiler_port, const GetInfo *pgi=nullptr)
Initialize.
Definition tracer.cpp:56
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
Definition dfs.hpp:68
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition lds.hpp:69
void constrain(const T &b)
Constrain future portfolio solutions to be better than b.
Definition pbs.hpp:612
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition pbs.hpp:562
PBS(T *s, SEBs &sebs, const Search::Options &o=Search::Options::def)
Definition pbs.hpp:606
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition pbs.hpp:510
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition rbs.hpp:96
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition tracer.hpp:165
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition tracer.hpp:278
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).
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Definition build.hpp:55
Builder(const Options &opt, bool best)
Initialize with options opt and best solution search support.
Definition build.hpp:37
static const unsigned long long int n_start
Number of pre-computed luby values.
Definition search.hh:577
static unsigned long long int log(unsigned long long int i)
Compute binary logarithm of i.
Definition cutoff.hpp:60
static unsigned long long int luby(unsigned long long int i)
Compute Luby number for step i.
Definition cutoff.hpp:68
CutoffRandom(unsigned int seed, unsigned long long int min, unsigned long long int max, unsigned long long int n)
Constructor.
Definition cutoff.hpp:88
Base class for cutoff generators for restart-based meta engine.
Definition search.hh:480
static Cutoff * luby(unsigned long long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
Definition cutoff.cpp:156
static Cutoff * repeat(Cutoff *c, unsigned long long int n)
Create generator that repeats n times each cutoff value from c.
Definition cutoff.cpp:179
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
Definition cutoff.cpp:175
static Cutoff * constant(unsigned long long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition cutoff.cpp:148
static Cutoff * linear(unsigned long long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
Definition cutoff.cpp:152
static Cutoff * rnd(unsigned int seed, unsigned long long int min, unsigned long long int max, unsigned long long int n)
Definition cutoff.cpp:164
static Cutoff * append(Cutoff *c1, unsigned long long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
Definition cutoff.cpp:171
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
Recorder for a search tracer with edge information.
Definition trace-recorder.hpp:93
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception).
Definition engine.cpp:48
virtual bool limited(void) const
Whether the engine stopped at a local limit (such as a CABS width limit) and cannot continue.
Definition engine.cpp:54
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).
Definition engine.cpp:60
virtual bool stopped(void) const =0
Check whether engine has been stopped.
WorkerControl worker_control
Control retained for the lifetime of a leaf engine.
Definition search.hh:1066
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition stop.cpp:79
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
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
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
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
Definition stop.cpp:69
unsigned long int frontier_limit
Maximal number of stored nodes for CABS (zero for no limit).
Definition search.hh:886
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Definition search.hh:882
unsigned int d_l
Discrepancy limit (for LDS, reaching it does not stop the engine).
Definition search.hh:867
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:865
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition stop.cpp:101
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.
Definition stop.cpp:55
static Stop * node(unsigned long long int l)
Stop if node limit l has been exceeded.
Definition stop.cpp:47
static Stop * fail(unsigned long long int l)
Stop if failure limit l has been exceeded.
Definition stop.cpp:51
static Stop * restart(unsigned long long int l)
Stop if restart limit l has been exceeded.
Definition stop.cpp:59
virtual bool stop(const Statistics &s, const Options &o)
Return true if time limit is exceeded.
Definition stop.cpp:89
TimeStop(double l)
Stop if search exceeds l milliseconds (from creation of this object).
Definition stop.hpp:110
External control for the requested number of search workers.
Definition search.hh:773
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).
Definition worker-control.cpp:95
void request(unsigned int workers)
Request workers workers (zero pauses the engine).
Definition worker-control.cpp:101
Recorder for engine events (for access control).
Definition trace-recorder.hpp:37
StdSearchTracer(std::ostream &os=std::cerr)
Initialize with output stream os.
Definition tracer.cpp:45
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)
The engine creates a new node with information ei and ni.
Definition tracer.cpp:82
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
Array with arbitrary number of elements.
Definition dynamic-array.hpp:44
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:618
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
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:128
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:123
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 nogoods_limit
Depth limit for no-good generation during search.
Definition search.hh:139
Sequential meta search engine implementations
Definition search.hh:101
Engine * sequential(T *master, const Search::Statistics &stat, Options &opt)
Build a sequential engine.
Engine * parallel(T *master, const Search::Statistics &stat, Options &opt)
Build a parallel engine.
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition build.hpp:55
Gecode toplevel namespace
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 .
Definition arithmetic.cpp:67
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 .
Definition arithmetic.cpp:49
Definition flatzinc.cpp:57
