Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
search.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2015-01-05 07:32:41 +0100 (Mon, 05 Jan 2015) $ by $Author: tack $
13  * $Revision: 14336 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_SEARCH_HH__
41 #define __GECODE_SEARCH_HH__
42 
43 #include <gecode/kernel.hh>
44 
45 /*
46  * Configure linking
47  *
48  */
49 #if !defined(GECODE_STATIC_LIBS) && \
50  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
51 
52 #ifdef GECODE_BUILD_SEARCH
53 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
54 #else
55 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
56 #endif
57 
58 #else
59 
60 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
61 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
62 #else
63 #define GECODE_SEARCH_EXPORT
64 #endif
65 
66 #endif
67 
68 // Configure auto-linking
69 #ifndef GECODE_BUILD_SEARCH
70 #define GECODE_LIBRARY_NAME "Search"
72 #endif
73 
74 
75 namespace Gecode { namespace Search {
76 
78  namespace Sequential {}
79 
81  namespace Parallel {}
82 
84  namespace Meta {}
85 
91  namespace Config {
93  const bool clone = true;
95  const double threads = 1.0;
97  const unsigned int c_d = 8;
99  const unsigned int a_d = 2;
100 
102  const unsigned int steal_limit = 3;
104  const unsigned int initial_delay = 5;
105 
107  const unsigned int nogoods_limit = 128;
108  }
109 
110 }}
111 
112 namespace Gecode { namespace Search {
113 
119  class GECODE_VTABLE_EXPORT UninitializedCutoff : public Exception {
121  public:
123  UninitializedCutoff(const char* l);
124  };
126 }}
127 
129 
130 namespace Gecode { namespace Search {
131 
136  class Statistics : public StatusStatistics {
137  public:
139  unsigned long int fail;
141  unsigned long int node;
143  unsigned long int depth;
145  unsigned long int restart;
147  unsigned long int nogood;
149  Statistics(void);
151  void reset(void);
153  Statistics operator +(const Statistics& s);
155  Statistics& operator +=(const Statistics& s);
156  };
157 
158 }}
159 
161 
162 namespace Gecode { namespace Search {
163 
164  class Stop;
165  class Cutoff;
166 
204  class Options {
205  public:
207  bool clone;
209  double threads;
211  unsigned int c_d;
213  unsigned int a_d;
215  unsigned int nogoods_limit;
223  Options(void);
226  expand(void) const;
227  };
228 
229 }}
230 
231 #include <gecode/search/options.hpp>
232 
233 namespace Gecode {
234 
235  template<template<class> class E, class T>
236  class RBS;
237 
238 }
239 
240 namespace Gecode { namespace Search { namespace Meta {
241 
242  class RBS;
243 
244 }}}
245 
246 namespace Gecode { namespace Search {
247 
263  public:
265  Stop(void);
267  virtual bool stop(const Statistics& s, const Options& o) = 0;
269  virtual ~Stop(void);
271  static void* operator new(size_t s);
273  static void operator delete(void* p);
274  };
275 
285  protected:
287  unsigned long int l;
288  public:
290  NodeStop(unsigned long int l);
292  unsigned long int limit(void) const;
294  void limit(unsigned long int l);
296  virtual bool stop(const Statistics& s, const Options& o);
297  };
298 
308  protected:
310  unsigned long int l;
311  public:
313  FailStop(unsigned long int l);
315  unsigned long int limit(void) const;
317  void limit(unsigned long int l);
319  virtual bool stop(const Statistics& s, const Options& o);
320  };
321 
327  protected:
331  unsigned long int l;
332  public:
334  TimeStop(unsigned long int l);
336  unsigned long int limit(void) const;
338  void limit(unsigned long int l);
340  void reset(void);
342  virtual bool stop(const Statistics& s, const Options& o);
343  };
344 
350  template<template<class>class,class> friend class ::Gecode::RBS;
351  friend class ::Gecode::Search::Meta::RBS;
352  private:
354  FailStop* e_stop;
356  Stop* m_stop;
358  bool e_stopped;
360  Statistics m_stat;
361  public:
363  MetaStop(Stop* s);
365  virtual bool stop(const Statistics& s, const Options& o);
367  void limit(const Search::Statistics& s, unsigned long int l);
369  void update(const Search::Statistics& s);
371  Stop* enginestop(void) const;
373  bool enginestopped(void) const;
375  Statistics metastatistics(void) const;
377  ~MetaStop(void);
378  };
379 
380 }}
381 
382 #include <gecode/search/stop.hpp>
383 
384 namespace Gecode { namespace Search {
385 
390  public:
392  Cutoff(void);
394  virtual unsigned long int operator ()(void) const = 0;
396  virtual unsigned long int operator ++(void) = 0;
398  virtual ~Cutoff(void);
400  static Cutoff*
401  constant(unsigned long int scale=1U);
403  static Cutoff*
404  linear(unsigned long int scale=1U);
408  static Cutoff*
409  geometric(unsigned long int scale=1U, double base=1.5);
411  static Cutoff*
412  luby(unsigned long int scale=1U);
417  static Cutoff*
418  rnd(unsigned int seed,
419  unsigned long int min, unsigned long int max,
420  unsigned long int n);
422  static Cutoff*
423  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
425  static Cutoff*
426  merge(Cutoff* c1, Cutoff* c2);
428  static Cutoff*
429  repeat(Cutoff* c, unsigned long int n);
431  static void* operator new(size_t s);
433  static void operator delete(void* p);
434  };
435 
436 }}
437 
438 #include <gecode/search/cutoff.hpp>
439 
440 namespace Gecode { namespace Search {
441 
445  class Engine {
446  public:
448  virtual Space* next(void) = 0;
450  virtual Statistics statistics(void) const = 0;
452  virtual bool stopped(void) const = 0;
454  virtual void reset(Space* s) = 0;
456  virtual NoGoods& nogoods(void) = 0;
458  virtual ~Engine(void) {}
459  };
460 
461 }}
462 
463 namespace Gecode {
464 
468  class EngineBase {
469  template<template<class>class,class> friend class ::Gecode::RBS;
470  protected:
474  ~EngineBase(void);
476  EngineBase(Search::Engine* e = NULL);
477  };
478 
479 }
480 
482 
483 namespace Gecode {
484 
485 
493  template<class T>
494  class DFS : public EngineBase {
495  public:
497  DFS(T* s, const Search::Options& o=Search::Options::def);
499  T* next(void);
501  Search::Statistics statistics(void) const;
503  bool stopped(void) const;
505  NoGoods& nogoods(void);
506  };
507 
509  template<class T>
510  T* dfs(T* s, const Search::Options& o=Search::Options::def);
511 
512 }
513 
514 #include <gecode/search/dfs.hpp>
515 
516 namespace Gecode {
517 
529  template<class T>
530  class BAB : public EngineBase {
531  public:
533  BAB(T* s, const Search::Options& o=Search::Options::def);
535  T* next(void);
537  Search::Statistics statistics(void) const;
539  bool stopped(void) const;
541  NoGoods& nogoods(void);
542  };
543 
556  template<class T>
557  T* bab(T* s, const Search::Options& o=Search::Options::def);
558 
559 }
560 
561 #include <gecode/search/bab.hpp>
562 
563 namespace Gecode {
564 
583  template<template<class> class E, class T>
584  class RBS : public EngineBase {
585  public:
587  RBS(T* s, const Search::Options& o);
589  T* next(void);
591  Search::Statistics statistics(void) const;
593  bool stopped(void) const;
594  };
595 
614  template<template<class> class E, class T>
615  T* rbs(T* s, const Search::Options& o);
616 
617 }
618 
619 #include <gecode/search/rbs.hpp>
620 
621 #endif
622 
623 // STATISTICS: search-other
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:213
bool stopped(void) const
Check whether engine has been stopped.
Definition: rbs.hpp:95
Search engine implementation interface
Definition: search.hh:445
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:215
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Search::Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:58
Search engine statistics
Definition: search.hh:136
Stop-object based on number of nodes
Definition: search.hh:284
Meta-engine performing restart-based search.
Definition: search.hh:236
#define GECODE_SEARCH_EXPORT
Definition: search.hh:63
Search::Engine * e
The actual search engine.
Definition: search.hh:472
virtual ~Engine(void)
Destructor.
Definition: search.hh:458
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:211
Search engine options
Definition: search.hh:204
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
unsigned long int l
Current limit in milliseconds.
Definition: search.hh:331
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
Search::Statistics statistics(void) const
Return statistics.
Definition: rbs.hpp:89
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:104
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:139
unsigned long int nogood
Number of no-goods posted.
Definition: search.hh:147
Support::Timer t
Time when execution should stop.
Definition: search.hh:329
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:143
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:389
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
Definition: statistics.hpp:54
Computation spaces.
Definition: core.hpp:1362
Statistics for execution of status
Definition: core.hpp:1310
Gecode::FloatVal c(-8, 8)
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:219
double threads
Number of threads to use.
Definition: search.hh:209
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Depth-first branch-and-bound search engine.
Definition: search.hh:530
Statistics(void)
Initialize.
Definition: statistics.hpp:49
static const Options def
Default options.
Definition: search.hh:221
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
Stop-object for meta engine
Definition: search.hh:349
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:207
virtual void reset(Space *s)=0
Reset engine to restart at space s.
~EngineBase(void)
Destructor.
Definition: engine-base.hpp:48
virtual NoGoods & nogoods(void)=0
Return no-goods.
EngineBase(Search::Engine *e=NULL)
Constructor.
Definition: engine-base.hpp:45
const double threads
Number of threads to use.
Definition: search.hh:95
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
Definition: dfs.hpp:77
T * next(void)
Return next solution (NULL, if non exists or search has been stopped)
Definition: rbs.hpp:83
T * bab(T *s, const Search::Options &o)
Perform depth-first branch-and-bound search for subclass T of space s and options o...
Definition: bab.hpp:81
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition: bab.hpp:51
bool stopped(void) const
Check whether engine has been stopped.
Definition: dfs.hpp:64
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
bool stopped(void) const
Check whether engine has been stopped.
Definition: bab.hpp:68
Options expand(void) const
Expand with real number of threads.
Definition: options.cpp:47
No-goods recorded from restarts.
Definition: core.hpp:1240
unsigned long int l
Node limit.
Definition: search.hh:287
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
unsigned long int l
Failure limit.
Definition: search.hh:310
Statistics operator+(const Statistics &s)
Return sum with s.
Definition: statistics.hpp:65
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition: rbs.hpp:52
Search::Statistics statistics(void) const
Return statistics.
Definition: bab.hpp:62
NoGoods & nogoods(void)
Return no-goods.
Definition: bab.hpp:74
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:97
unsigned long int restart
Number of restarts.
Definition: search.hh:145
Base-class for search engines.
Definition: search.hh:468
Stop * stop
Stop object for stopping search.
Definition: search.hh:217
virtual Statistics statistics(void) const =0
Return statistics.
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:141
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:107
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:70
T * next(void)
Return next better solution (NULL, if none exists or search has been stopped)
Definition: bab.hpp:56
Stop-object based on time
Definition: search.hh:326
Base-class for Stop-object.
Definition: search.hh:262
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:102
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:102
Depth-first search engine.
Definition: search.hh:494
Stop-object based on number of failures
Definition: search.hh:307
Options(void)
Initialize with default values.
Definition: options.hpp:41
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
Definition: dfs.hpp:47
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:93
void reset(void)
Reset.
Definition: statistics.hpp:43
virtual bool stopped(void) const =0
Check whether engine has been stopped.