Generated on Fri Jun 5 2015 21:15:11 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-03-17 11:17:00 +0100 (Tue, 17 Mar 2015) $ by $Author: tack $
13  * $Revision: 14443 $
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 
169  public:
171 
172  Cutoff(void);
175  virtual unsigned long int operator ()(void) const = 0;
177  virtual unsigned long int operator ++(void) = 0;
179  virtual ~Cutoff(void);
181 
183  static void* operator new(size_t s);
186  static void operator delete(void* p);
188 
190  static Cutoff*
192  constant(unsigned long int scale=1U);
194  static Cutoff*
195  linear(unsigned long int scale=1U);
199  static Cutoff*
200  geometric(unsigned long int scale=1U, double base=1.5);
202  static Cutoff*
203  luby(unsigned long int scale=1U);
208  static Cutoff*
209  rnd(unsigned int seed,
210  unsigned long int min, unsigned long int max,
211  unsigned long int n);
213  static Cutoff*
214  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
216  static Cutoff*
217  merge(Cutoff* c1, Cutoff* c2);
219  static Cutoff*
220  repeat(Cutoff* c, unsigned long int n);
222  };
223 
229  protected:
231  unsigned long int c;
232  public:
234  CutoffConstant(unsigned long int c);
236  virtual unsigned long int operator ()(void) const;
238  virtual unsigned long int operator ++(void);
239  };
240 
246  protected:
248  unsigned long int scale;
250  unsigned long int n;
251  public:
253  CutoffLinear(unsigned long int scale);
255  virtual unsigned long int operator ()(void) const;
257  virtual unsigned long int operator ++(void);
258  };
259 
265  protected:
267  unsigned long int i;
269  unsigned long int scale;
271  static const unsigned long int n_start = 63U;
273  static unsigned long int start[n_start];
275  static unsigned long int log(unsigned long int i);
277  static unsigned long int luby(unsigned long int i);
278  public:
280  CutoffLuby(unsigned long int scale);
282  virtual unsigned long int operator ()(void) const;
284  virtual unsigned long int operator ++(void);
285  };
286 
292  protected:
294  double n;
296  double scale;
298  double base;
299  public:
301  CutoffGeometric(unsigned long int scale, double base);
303  virtual unsigned long int operator ()(void) const;
305  virtual unsigned long int operator ++(void);
306  };
307 
313  protected:
317  unsigned long int min;
319  unsigned long int n;
321  unsigned long int step;
323  unsigned long int cur;
324  public:
326  CutoffRandom(unsigned int seed,
327  unsigned long int min, unsigned long int max,
328  unsigned long int n);
330  virtual unsigned long int operator ()(void) const;
332  virtual unsigned long int operator ++(void);
333  };
334 
340  protected:
346  unsigned long int n;
347  public:
349  CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
351  virtual unsigned long int operator ()(void) const;
353  virtual unsigned long int operator ++(void);
355  virtual ~CutoffAppend(void);
356  };
357 
363  protected:
368  public:
370  CutoffMerge(Cutoff* c1, Cutoff* c2);
372  virtual unsigned long int operator ()(void) const;
374  virtual unsigned long int operator ++(void);
376  virtual ~CutoffMerge(void);
377  };
378 
384  protected:
387  // Current cutoff
388  unsigned int cutoff;
389  // Iteration
390  unsigned long int i;
391  // Number of repetitions
392  unsigned long int n;
393  public:
395  CutoffRepeat(Cutoff* c, unsigned long int n);
397  virtual unsigned long int operator ()(void) const;
399  virtual unsigned long int operator ++(void);
401  virtual ~CutoffRepeat(void);
402  };
403 
404 }}
405 
406 #include <gecode/search/cutoff.hpp>
407 
408 namespace Gecode { namespace Search {
409 
410  class Stop;
411 
449  class Options {
450  public:
452  bool clone;
454  double threads;
456  unsigned int c_d;
458  unsigned int a_d;
460  unsigned int nogoods_limit;
468  Options(void);
471  expand(void) const;
472  };
473 
474 }}
475 
476 #include <gecode/search/options.hpp>
477 
478 namespace Gecode { namespace Search {
479 
495  public:
497 
498  Stop(void);
501  virtual bool stop(const Statistics& s, const Options& o) = 0;
503  virtual ~Stop(void);
505 
507  static void* operator new(size_t s);
510  static void operator delete(void* p);
512 
514  static Stop* node(unsigned long int l);
517  static Stop* fail(unsigned long int l);
519  static Stop* time(unsigned long int l);
521  };
522 
532  protected:
534  unsigned long int l;
535  public:
537  NodeStop(unsigned long int l);
539  unsigned long int limit(void) const;
541  void limit(unsigned long int l);
543  virtual bool stop(const Statistics& s, const Options& o);
544  };
545 
555  protected:
557  unsigned long int l;
558  public:
560  FailStop(unsigned long int l);
562  unsigned long int limit(void) const;
564  void limit(unsigned long int l);
566  virtual bool stop(const Statistics& s, const Options& o);
567  };
568 
574  protected:
578  unsigned long int l;
579  public:
581  TimeStop(unsigned long int l);
583  unsigned long int limit(void) const;
585  void limit(unsigned long int l);
587  void reset(void);
589  virtual bool stop(const Statistics& s, const Options& o);
590  };
591 
592 }}
593 
594 #include <gecode/search/stop.hpp>
595 
596 namespace Gecode { namespace Search {
597 
602  public:
604  virtual Space* next(void) = 0;
606  virtual Statistics statistics(void) const = 0;
608  virtual bool stopped(void) const = 0;
610  virtual void reset(Space* s);
612  virtual NoGoods& nogoods(void);
614  virtual ~Engine(void);
616 
617  static void* operator new(size_t s);
620  static void operator delete(void* p);
622  };
623 
624 }}
625 
626 #include <gecode/search/engine.hpp>
627 
628 namespace Gecode {
629 
630  template<template<class> class E, class T>
631  class RBS;
632 
633 }
634 
635 namespace Gecode { namespace Search {
636 
638  template<class T>
639  class EngineBase {
640  template<template<class>class,class> friend class ::Gecode::RBS;
641  protected:
645  EngineBase(Engine* e = NULL);
646  public:
648  virtual T* next(void);
650  virtual Statistics statistics(void) const;
652  virtual bool stopped(void) const;
654  virtual NoGoods& nogoods(void);
656  virtual ~EngineBase(void);
658 
659  static void* operator new(size_t s);
662  static void operator delete(void* p);
664  };
665 
666 }}
667 
669 
670 namespace Gecode {
671 
672 
680  template<class T>
681  class DFS : public Search::EngineBase<T> {
682  public:
684  DFS(T* s, const Search::Options& o=Search::Options::def);
685  };
686 
688  template<class T>
689  T* dfs(T* s, const Search::Options& o=Search::Options::def);
690 
691 }
692 
693 #include <gecode/search/dfs.hpp>
694 
695 namespace Gecode {
696 
708  template<class T>
709  class BAB : public Search::EngineBase<T> {
710  public:
712  BAB(T* s, const Search::Options& o=Search::Options::def);
713  };
714 
727  template<class T>
728  T* bab(T* s, const Search::Options& o=Search::Options::def);
729 
730 }
731 
732 #include <gecode/search/bab.hpp>
733 
734 namespace Gecode {
735 
754  template<template<class> class E, class T>
755  class RBS : public Search::EngineBase<T> {
756  using Search::EngineBase<T>::e;
757  public:
759  RBS(T* s, const Search::Options& o);
760  };
761 
780  template<template<class> class E, class T>
781  T* rbs(T* s, const Search::Options& o);
782 
783 }
784 
785 #include <gecode/search/rbs.hpp>
786 
787 #endif
788 
789 // STATISTICS: search-other
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:458
double scale
Scale factor.
Definition: search.hh:296
Search engine implementation interface
Definition: search.hh:601
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:460
unsigned long int scale
Scale factor.
Definition: search.hh:248
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 engine statistics
Definition: search.hh:136
Stop-object based on number of nodes
Definition: search.hh:531
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:151
Meta-engine performing restart-based search.
Definition: search.hh:631
#define GECODE_SEARCH_EXPORT
Definition: search.hh:63
Cutoff * c1
First cutoff generator.
Definition: search.hh:365
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:456
Cutoff generator appending two cutoff generators.
Definition: search.hh:339
Search engine options
Definition: search.hh:449
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:578
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
unsigned long int step
Step size.
Definition: search.hh:321
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:104
unsigned long int scale
Scale factor.
Definition: search.hh:269
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:576
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:143
Cutoff generator for the Luby sequence.
Definition: search.hh:264
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:168
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
Definition: statistics.hpp:54
unsigned long int min
Minimum cutoff value.
Definition: search.hh:317
unsigned long int c
Constant.
Definition: search.hh:231
Computation spaces.
Definition: core.hpp:1362
virtual ~EngineBase(void)
Destructor.
Definition: engine-base.hpp:70
unsigned long int n
Random values.
Definition: search.hh:319
Statistics for execution of status
Definition: core.hpp:1310
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: engine-base.hpp:50
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Definition: search.hh:362
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:464
double threads
Number of threads to use.
Definition: search.hh:454
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Cutoff generator for the random sequence.
Definition: search.hh:312
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual Statistics statistics(void) const
Return statistics.
Definition: engine-base.hpp:55
Depth-first branch-and-bound search engine.
Definition: search.hh:709
Statistics(void)
Initialize.
Definition: statistics.hpp:49
static const Options def
Default options.
Definition: search.hh:466
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
Base-class for search engines.
Definition: search.hh:639
unsigned long int i
Definition: search.hh:390
unsigned long int n
How many number to take from the first.
Definition: search.hh:346
unsigned long int cur
Current value.
Definition: search.hh:323
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:315
unsigned long int i
Iteration number.
Definition: search.hh:267
double n
Current cutoff value.
Definition: search.hh:294
Engine * e
The actual search engine.
Definition: search.hh:643
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:452
Template for linear congruential generators.
Definition: random.hpp:50
Cutoff * c2
Second cutoff generators.
Definition: search.hh:344
Cutoff * c1
First cutoff generators.
Definition: search.hh:342
Cutoff generator for linear sequence.
Definition: search.hh:245
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:52
Cutoff generator for the geometric sequence.
Definition: search.hh:291
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:56
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
Definition: bab.hpp:51
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Cutoff * c
Actual cutoff generator.
Definition: search.hh:386
Cutoff generator for constant sequence.
Definition: search.hh:228
unsigned long int n
Next number in sequence.
Definition: search.hh:250
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:534
unsigned long int l
Failure limit.
Definition: search.hh:557
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:47
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:383
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
Stop * stop
Stop object for stopping search.
Definition: search.hh:462
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
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: engine-base.hpp:60
unsigned long int n
Definition: search.hh:392
Stop-object based on time
Definition: search.hh:573
Base-class for Stop-object.
Definition: search.hh:494
Cutoff * c2
Second cutoff generator.
Definition: search.hh:367
virtual NoGoods & nogoods(void)
Return no-goods (the no-goods are empty)
Definition: engine-base.hpp:65
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:102
EngineBase(Engine *e=NULL)
Constructor.
Definition: engine-base.hpp:46
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:79
Depth-first search engine.
Definition: search.hh:681
Stop-object based on number of failures
Definition: search.hh:554
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