46 #ifndef __GECODE_SEARCH_HH__ 47 #define __GECODE_SEARCH_HH__ 55 #if !defined(GECODE_STATIC_LIBS) && \ 56 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER)) 58 #ifdef GECODE_BUILD_SEARCH 59 #define GECODE_SEARCH_EXPORT __declspec( dllexport ) 61 #define GECODE_SEARCH_EXPORT __declspec( dllimport ) 66 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY 67 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default"))) 69 #define GECODE_SEARCH_EXPORT 75 #ifndef GECODE_BUILD_SEARCH 76 #define GECODE_LIBRARY_NAME "Search" 81 namespace Gecode {
namespace Search {
84 namespace Sequential {}
95 namespace Sequential {}
115 const unsigned int c_d = 8;
117 const unsigned int a_d = 2;
125 const unsigned int d_l = 5;
143 namespace Gecode {
namespace Search {
175 namespace Gecode {
namespace Search {
222 bool meta(
void)
const;
226 unsigned int wfst(
void)
const;
229 unsigned int wlst(
void)
const;
231 unsigned int workers(
void)
const;
235 unsigned int efst(
void)
const;
238 unsigned int elst(
void)
const;
240 unsigned int engines(
void)
const;
256 void init(
unsigned int wid,
unsigned int nid,
unsigned int a);
258 void init(
unsigned int wid,
unsigned int nid,
unsigned int a,
261 void invalidate(
void);
265 EdgeInfo(
unsigned int wid,
unsigned int nid,
unsigned int a);
267 operator bool(
void)
const;
269 unsigned int wid(
void)
const;
271 unsigned int nid(
void)
const;
273 unsigned int alternative(
void)
const;
275 std::string string(
void)
const;
299 unsigned int wid,
unsigned int nid,
304 unsigned int wid(
void)
const;
306 unsigned int nid(
void)
const;
308 const Space& space(
void)
const;
310 const Choice& choice(
void)
const;
316 unsigned int pending;
322 unsigned int n_active;
330 void worker(
unsigned int& wid,
unsigned int& eid);
336 void _round(
unsigned int eid);
347 unsigned int workers(
void)
const;
350 unsigned int engines(
void)
const;
352 const EngineInfo& engine(
unsigned int eid)
const;
354 unsigned int eid(
unsigned int wid)
const;
358 virtual void init(
void) = 0;
361 virtual void round(
unsigned int eid) = 0;
363 virtual void skip(
const EdgeInfo& ei) = 0;
367 virtual void done(
void) = 0;
378 static const char* t2s[EngineType::AOE + 1];
383 virtual void init(
void);
385 virtual void round(
unsigned int eid);
387 virtual void skip(
const EdgeInfo& ei);
391 virtual void done(
void);
403 #ifdef GECODE_HAS_CPPROFILER 408 namespace CPProfiler {}
412 namespace Gecode {
namespace CPProfiler {
430 virtual std::string getInfo(
const Space& home)
const = 0;
451 virtual void init(
void);
453 virtual void round(
unsigned int eid);
455 virtual void skip(
const EdgeInfo& ei);
459 virtual void done(
void);
468 namespace Gecode {
namespace Search {
481 virtual unsigned long int operator ()(
void)
const = 0;
483 virtual unsigned long int operator ++(
void) = 0;
508 rnd(
unsigned int seed,
509 unsigned long int min,
unsigned long int max,
510 unsigned long int n);
519 repeat(
Cutoff*
c,
unsigned long int n);
535 virtual unsigned long int operator ()(
void)
const;
537 virtual unsigned long int operator ++(
void);
554 virtual unsigned long int operator ()(
void)
const;
556 virtual unsigned long int operator ++(
void);
570 static const unsigned long int n_start = 63U;
572 static unsigned long int start[n_start];
574 static unsigned long int log(
unsigned long int i);
576 static unsigned long int luby(
unsigned long int i);
581 virtual unsigned long int operator ()(
void)
const;
583 virtual unsigned long int operator ++(
void);
602 virtual unsigned long int operator ()(
void)
const;
604 virtual unsigned long int operator ++(
void);
626 unsigned long int min,
unsigned long int max,
627 unsigned long int n);
629 virtual unsigned long int operator ()(
void)
const;
631 virtual unsigned long int operator ++(
void);
650 virtual unsigned long int operator ()(
void)
const;
652 virtual unsigned long int operator ++(
void);
671 virtual unsigned long int operator ()(
void)
const;
673 virtual unsigned long int operator ++(
void);
696 virtual unsigned long int operator ()(
void)
const;
698 virtual unsigned long int operator ++(
void);
707 namespace Gecode {
namespace Search {
785 namespace Gecode {
namespace Search {
814 static Stop* node(
unsigned long int l);
817 static Stop* fail(
unsigned long int l);
819 static Stop* time(
unsigned long int l);
839 unsigned long int limit(
void)
const;
841 void limit(
unsigned long int l);
862 unsigned long int limit(
void)
const;
864 void limit(
unsigned long int l);
883 unsigned long int limit(
void)
const;
885 void limit(
unsigned long int l);
896 namespace Gecode {
namespace Search {
904 virtual Space* next(
void) = 0;
906 virtual Statistics statistics(
void)
const = 0;
908 virtual bool stopped(
void)
const = 0;
910 virtual void constrain(
const Space&
b);
912 virtual void reset(
Space* s);
914 virtual NoGoods& nogoods(
void);
923 namespace Gecode {
namespace Search {
928 template<
class,
class>
930 template<
class,
template<
class>
class>
939 virtual T* next(
void);
943 virtual bool stopped(
void)
const;
957 namespace Gecode {
namespace Search {
960 template<
class T,
class E>
963 template<
class T,
template<
class>
class E>
979 const Options& options(
void)
const;
981 bool best(
void)
const;
1011 explicit SEBs(
int n);
1013 SEBs(
const std::vector<SEB>&
x);
1015 template<
class InputIterator>
1016 SEBs(InputIterator first, InputIterator last);
1044 static const bool best =
false;
1078 static const bool best =
true;
1116 static const bool best =
false;
1154 template<
class T,
template<
class>
class E =
DFS>
1161 static const bool best = E<T>::best;
1182 template<
class T,
template<
class>
class E>
1186 template<
class T,
template<
class>
class E>
1193 namespace Gecode {
namespace Search {
namespace Meta {
1196 template<
class T,
template<
class>
class E>
1200 template<
class T,
template<
class>
class E>
1204 #ifdef GECODE_HAS_THREADS 1207 template<
class T,
template<
class>
class E>
1211 template<
class T,
template<
class>
class E>
1238 template<
class T,
template<
class>
class E =
DFS>
1259 static const bool best = E<T>::best;
1279 template<
class T,
template<
class>
class E>
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
double scale
Scale factor.
const Space & _s
The corresponding space.
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Search engine implementation interface
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Limited discrepancy search engine.
unsigned long int scale
Scale factor.
Class to send solution information to CPProfiler.
Stop-object based on number of nodes
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Meta-engine performing restart-based search.
Meta engine using a portfolio of search engines.
#define GECODE_SEARCH_EXPORT
Node representing a branch.
Cutoff * c1
First cutoff generator.
Argument array for primtive types.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Cutoff generator appending two cutoff generators.
unsigned int _nid
The parent node id.
A class for building search engines.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Options opt
Stored and already expanded options.
unsigned long int l
Current limit in milliseconds.
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
unsigned long int step
Step size.
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
std::string _s
String corresponding to alternative.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
unsigned int slice
Size of a slice in a portfolio (in number of failures)
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
unsigned long int scale
Scale factor.
unsigned long int fail
Number of failed nodes in search tree.
unsigned long int nogood
Number of no-goods posted.
Support::Timer t
Time when execution should stop.
Node representing failure.
unsigned long int depth
Maximum depth of search stack.
Array with arbitrary number of elements.
Cutoff generator for the Luby sequence.
Base class for cutoff generators for restart-based meta engine.
unsigned long int min
Minimum cutoff value.
Class to record search trace info for CPProfiler.
EngineType
Which type of engine.
unsigned long int c
Constant.
unsigned int d_l
Discrepancy limit (for LDS)
unsigned long int n
Random values.
Statistics for execution of status
A mutex for mutual exclausion among several threads.
std::string expand(Gecode::IntRelType irt)
Expand relation to abbreviation.
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Cutoff * cutoff
Cutoff for restart-based search.
double threads
Number of threads to use.
const bool b
Whether engine to be built is a best solution search engine.
const unsigned int cpprofiler_port
Default port for CPProfiler.
Cutoff generator for the random sequence.
int n
Number of negative literals for node type.
Recorder for a search tracer with edge information.
Base-class for search engines.
Depth-first branch-and-bound search engine.
FloatVal operator+(const FloatVal &x)
Simple recorder for a search tracer.
static const Options def
Default options.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Node representing a solution.
unsigned long int n
How many number to take from the first.
unsigned long int cur
Current value.
Support::RandomGenerator rnd
Random number generator.
EngineType _type
The engine type.
unsigned long int i
Iteration number.
double n
Current cutoff value.
bool clone
Whether engines create a clone when being initialized.
Template for linear congruential generators.
Search::Builder * SEB
Type for a search engine builder.
const unsigned int d_l
Default discrepancy limit for LDS.
unsigned int _a
Number of alternative.
Cutoff * c2
Second cutoff generators.
unsigned int _lst
Last worker or engine.
SearchTracer * tracer
Tracer object for tracing search.
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Cutoff * c1
First cutoff generators.
Cutoff generator for linear sequence.
const double threads
Number of threads to use.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
Support for tracing search.
unsigned int assets
Number of assets (engines) in a portfolio.
Cutoff generator for the geometric sequence.
T * bab(T *s, const Search::Options &o)
Perform depth-first branch-and-bound search for subclass T of space s and options o...
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Cutoff * c
Actual cutoff generator.
Cutoff generator for constant sequence.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
const double base
Base for geometric restart sequence.
unsigned long int n
Next number in sequence.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
No-goods recorded from restarts.
unsigned long int l
Node limit.
Engine * e
The actual search engine.
unsigned int _wid
The worker id.
unsigned long int l
Failure limit.
std::ostream & os
Output stream to use.
Cutoff generator that repeats a cutoff from another cutoff generator.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Post propagator for SetVar x
Recorder for engine events (for access control)
unsigned long int restart
Number of restarts.
Passing search engine builder arguments.
unsigned int _nid
The node id.
Stop * stop
Stop object for stopping search.
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Information about an engine.
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Stop-object based on time
Base-class for Stop-object.
Cutoff * c2
Second cutoff generator.
NodeType _nt
The node type.
Base class for heap allocated objects.
static StdSearchTracer def
Default tracer (printing to std::cerr)
const unsigned int steal_limit
Minimal number of open nodes for stealing.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Depth-first search engine.
unsigned int _fst
First worker or engine.
Stop-object based on number of failures
const bool clone
Whether engines create a clone when being initialized.