Go to the documentation of this file.
40 #ifndef __GECODE_SEARCH_HH__
41 #define __GECODE_SEARCH_HH__
49 #if !defined(GECODE_STATIC_LIBS) && \
50 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
52 #ifdef GECODE_BUILD_SEARCH
53 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
55 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
60 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
61 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
63 #define GECODE_SEARCH_EXPORT
69 #ifndef GECODE_BUILD_SEARCH
70 #define GECODE_LIBRARY_NAME "Search"
75 namespace Gecode {
namespace Search {
78 namespace Sequential {}
89 namespace Sequential {}
109 const unsigned int c_d = 8;
111 const unsigned int a_d = 2;
119 const unsigned int d_l = 5;
134 namespace Gecode {
namespace Search {
166 namespace Gecode {
namespace Search {
179 virtual unsigned long int operator ()(
void)
const = 0;
181 virtual unsigned long int operator ++(
void) = 0;
206 rnd(
unsigned int seed,
207 unsigned long int min,
unsigned long int max,
208 unsigned long int n);
217 repeat(
Cutoff*
c,
unsigned long int n);
233 virtual unsigned long int operator ()(
void)
const;
235 virtual unsigned long int operator ++(
void);
252 virtual unsigned long int operator ()(
void)
const;
254 virtual unsigned long int operator ++(
void);
268 static const unsigned long int n_start = 63U;
270 static unsigned long int start[n_start];
272 static unsigned long int log(
unsigned long int i);
274 static unsigned long int luby(
unsigned long int i);
279 virtual unsigned long int operator ()(
void)
const;
281 virtual unsigned long int operator ++(
void);
300 virtual unsigned long int operator ()(
void)
const;
302 virtual unsigned long int operator ++(
void);
324 unsigned long int min,
unsigned long int max,
325 unsigned long int n);
327 virtual unsigned long int operator ()(
void)
const;
329 virtual unsigned long int operator ++(
void);
348 virtual unsigned long int operator ()(
void)
const;
350 virtual unsigned long int operator ++(
void);
369 virtual unsigned long int operator ()(
void)
const;
371 virtual unsigned long int operator ++(
void);
394 virtual unsigned long int operator ()(
void)
const;
396 virtual unsigned long int operator ++(
void);
405 namespace Gecode {
namespace Search {
485 namespace Gecode {
namespace Search {
514 static Stop* node(
unsigned long int l);
517 static Stop* fail(
unsigned long int l);
519 static Stop* time(
unsigned long int l);
539 unsigned long int limit(
void)
const;
541 void limit(
unsigned long int l);
562 unsigned long int limit(
void)
const;
564 void limit(
unsigned long int l);
583 unsigned long int limit(
void)
const;
585 void limit(
unsigned long int l);
596 namespace Gecode {
namespace Search {
604 virtual Space* next(
void) = 0;
606 virtual Statistics statistics(
void)
const = 0;
608 virtual bool stopped(
void)
const = 0;
610 virtual void constrain(
const Space&
b);
612 virtual void reset(
Space* s);
614 virtual NoGoods& nogoods(
void);
623 namespace Gecode {
namespace Search {
628 template<
class,
class>
630 template<
class,
template<
class>
class>
639 virtual T*
next(
void);
643 virtual bool stopped(
void)
const;
657 namespace Gecode {
namespace Search {
660 template<
class T,
class E>
661 Engine*
build(Space* s,
const Options&
opt);
663 template<
class T,
template<
class>
class E>
664 Engine*
build(Space* s,
const Options&
opt);
679 const Options& options(
void)
const;
681 bool best(
void)
const;
711 explicit SEBs(
int n);
713 SEBs(
const std::vector<SEB>&
x);
715 template<
class InputIterator>
716 SEBs(InputIterator first, InputIterator last);
744 static const bool best =
false;
816 static const bool best =
false;
854 template<
class T,
template<
class>
class E = DFS>
861 static const bool best = E<T>::best;
882 template<
class T,
template<
class>
class E>
886 template<
class T,
template<
class>
class E>
893 namespace Gecode {
namespace Search {
namespace Meta {
896 template<
class T,
template<
class>
class E>
897 Engine*
sequential(T* master,
const Search::Statistics& stat, Options&
opt);
900 template<
class T,
template<
class>
class E>
902 const Search::Statistics& stat, Options&
opt,
bool best);
904 #ifdef GECODE_HAS_THREADS
907 template<
class T,
template<
class>
class E>
908 Engine*
parallel(T* master,
const Search::Statistics& stat, Options&
opt);
911 template<
class T,
template<
class>
class E>
912 Engine*
parallel(T* master, SEBs& sebs,
913 const Search::Statistics& stat, Options&
opt,
bool best);
938 template<
class T,
template<
class>
class E = DFS>
959 static const bool best = E<T>::best;
979 template<
class T,
template<
class>
class E>
Post propagator for SetVar x
Base(Engine *e=NULL)
Constructor.
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 long int l
Node limit.
Support::Timer t
Time when execution should stop.
#define GECODE_SEARCH_EXPORT
unsigned long int i
Iteration number.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
A class for building search engines.
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.
Argument array for primtive types.
bool share_pbs
Whether to share AFC information among assets in a portfolio.
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.
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Limited discrepancy search engine.
double scale
Scale factor.
Gecode::IntArgs i(4, 1, 2, 3, 4)
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.
Depth-first search engine.
Base-class for search engines.
Statistics operator+(const Statistics &s)
Return sum with s.
SEBs(void)
Allocate empty array.
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
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Gecode toplevel namespace
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.
No-goods recorded from restarts.
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
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.
Meta-engine performing restart-based search.
Meta engine using a portfolio of search engines.
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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)
unsigned long int c
Constant.
Template for linear congruential generators.
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 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 bool stopped(void) const
Check whether engine has been stopped.
Cutoff generator for the Luby sequence.
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.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
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.
Cutoff generator for the geometric sequence.
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.
virtual Statistics statistics(void) const
Return statistics.
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
bool share_rbs
Whether to share AFC information between restarts.
Cutoff generator for constant sequence.
static const bool best
Whether engine does best solution search.
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)
int n
Number of negative literals for node type.
bool clone
Whether engines create a clone when being initialized.
Cutoff * c
Actual cutoff generator.
unsigned int d_l
Discrepancy limit (for LDS)
Engine * e
The actual search engine.
Cutoff * c2
Second cutoff generators.
unsigned long int scale
Scale factor.
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.
const bool b
Whether engine to be built is a best solution search engine.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
unsigned long int min
Minimum cutoff value.