Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
pbs.hpp
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  *
6  * Copyright:
7  * Christian Schulte, 2015
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <cmath>
39 #include <algorithm>
40 
41 namespace Gecode { namespace Search {
42 
44  template<class T, template<class> class E>
45  class PbsBuilder : public Builder {
46  using Builder::opt;
47  public:
49  PbsBuilder(const Options& opt);
51  virtual Engine* operator() (Space* s) const;
52  };
53 
54  template<class T, template<class> class E>
55  inline
57  : Builder(opt,E<T>::best) {}
58 
59  template<class T, template<class> class E>
60  Engine*
62  return build<T,PBS<T,E> >(s,opt);
63  }
64 
65 }}
66 
68 
69 namespace Gecode { namespace Search { namespace Seq {
70 
73  pbsstop(Stop* so);
74 
77  pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves,
78  const Statistics& stat, const Search::Options& opt, bool best);
79 
80 }}}
81 
82 namespace Gecode { namespace Search { namespace Par {
83 
86  pbsstop(Stop* so);
87 
90  pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves,
91  const Statistics& stat, bool best);
92 
93 }}}
94 
95 namespace Gecode { namespace Search {
96 
97  template<class T, template<class> class E>
98  Engine*
99  pbsseq(T* master, const Search::Statistics& stat, Options& opt) {
100  Stop* stop = opt.stop;
101  Region r;
102 
103  // In case there are more threads than assets requested
104  opt.threads = std::max(floor(opt.threads /
105  static_cast<double>(opt.assets)),1.0);
106 
107  unsigned int n_slaves = opt.assets;
108  Engine** slaves = r.alloc<Engine*>(n_slaves);
109  Stop** stops = r.alloc<Stop*>(n_slaves);
110 
112  SearchTracer::EngineType::PBS, n_slaves);
113 
114  for (unsigned int i=0; i<n_slaves; i++) {
115  opt.stop = stops[i] = Seq::pbsstop(stop);
116  Space* slave = (i == n_slaves-1) ?
117  master : master->clone();
118  (void) slave->slave(i);
119  slaves[i] = build<T,E>(slave,opt);
120  }
121 
122  return Seq::pbsengine(slaves,stops,n_slaves,stat,opt,E<T>::best);
123  }
124 
125  template<class T, template<class> class E>
126  Engine*
127  pbsseq(T* master, SEBs& sebs,
128  const Search::Statistics& stat, Options& opt, bool best) {
129  Region r;
130 
131  int n_slaves = sebs.size();
132  Engine** slaves = r.alloc<Engine*>(n_slaves);
133  Stop** stops = r.alloc<Stop*>(n_slaves);
134 
136  SearchTracer::EngineType::PBS, n_slaves);
137 
138  for (int i=0; i<n_slaves; i++) {
139  // Re-configure slave options
140  stops[i] = Seq::pbsstop(sebs[i]->options().stop);
141  sebs[i]->options().stop = stops[i];
142  sebs[i]->options().clone = false;
143  Space* slave = (i == n_slaves-1) ?
144  master : master->clone();
145  (void) slave->slave(i);
146  slaves[i] = (*sebs[i])(slave);
147  delete sebs[i];
148  }
149 
150  return Seq::pbsengine(slaves,stops,n_slaves,stat,opt,best);
151  }
152 
153 #ifdef GECODE_HAS_THREADS
154 
155  template<class T, template<class> class E>
156  Engine*
157  pbspar(T* master, const Search::Statistics& stat, Options& opt) {
158  Stop* stop = opt.stop;
159  Region r;
160 
161  // Limit the number of slaves to the number of threads
162  unsigned int n_slaves = std::min(static_cast<unsigned int>(opt.threads),
163  opt.assets);
164  // Redistribute additional threads to slaves
165  opt.threads = floor(opt.threads / static_cast<double>(n_slaves));
166 
168  SearchTracer::EngineType::PBS, n_slaves);
169 
170  Engine** slaves = r.alloc<Engine*>(n_slaves);
171  Stop** stops = r.alloc<Stop*>(n_slaves);
172 
173  for (unsigned int i=0; i<n_slaves; i++) {
174  opt.stop = stops[i] = Par::pbsstop(stop);
175  Space* slave = (i == n_slaves-1) ?
176  master : master->clone();
177  (void) slave->slave(i);
178  slaves[i] = build<T,E>(slave,opt);
179  }
180 
181  return Par::pbsengine(slaves,stops,n_slaves,stat,E<T>::best);
182  }
183 
184  template<class T, template<class> class E>
185  Engine*
186  pbspar(T* master, SEBs& sebs,
187  const Search::Statistics& stat, Options& opt, bool best) {
188  Region r;
189 
190  // Limit the number of slaves to the number of threads
191  int n_slaves = std::min(static_cast<int>(opt.threads),
192  sebs.size());
193 
195  SearchTracer::EngineType::PBS, n_slaves);
196 
197  Engine** slaves = r.alloc<Engine*>(n_slaves);
198  Stop** stops = r.alloc<Stop*>(n_slaves);
199 
200  for (int i=0; i<n_slaves; i++) {
201  // Re-configure slave options
202  stops[i] = Par::pbsstop(sebs[i]->options().stop);
203  sebs[i]->options().stop = stops[i];
204  sebs[i]->options().clone = false;
205  Space* slave = (i == n_slaves-1) ?
206  master : master->clone();
207  (void) slave->slave(i);
208  slaves[i] = (*sebs[i])(slave);
209  delete sebs[i];
210  }
211  // Delete excess builders
212  for (int i=n_slaves; i<sebs.size(); i++)
213  delete sebs[i];
214 
215  return Par::pbsengine(slaves,stops,n_slaves,stat,best);
216  }
217 
218 #endif
219 
220 }}
221 
222 namespace Gecode {
223 
224  template<class T, template<class> class E>
225  PBS<T,E>::PBS(T* s, const Search::Options& o) {
227 
228  if (opt.assets == 0)
229  throw Search::NoAssets("PBS::PBS");
230 
231  Search::Statistics stat;
232 
233  if (s->status(stat) == SS_FAILED) {
234  stat.fail++;
235  if (!opt.clone)
236  delete s;
237  e = Search::Seq::dead(opt,stat);
238  return;
239  }
240 
241  // Check whether a clone must be used
242  T* master = opt.clone ?
243  dynamic_cast<T*>(s->clone()) : s;
244  opt.clone = false;
245 
246  // Always execute master function
247  (void) master->master(0);
248 
249  // No need to create a portfolio engine but must run slave function
250  if (o.assets == 1) {
251  (void) master->slave(0);
252  e = Search::build<T,E>(master,opt);
253  return;
254  }
255 
256 #ifdef GECODE_HAS_THREADS
257  if (opt.threads > 1.0)
258  e = Search::pbspar<T,E>(master,stat,opt);
259  else
260 #endif
261  e = Search::pbsseq<T,E>(master,stat,opt);
262  }
263 
264  template<class T, template<class> class E>
265  void
266  PBS<T,E>::build(T* s, SEBs& sebs, const Search::Options& o) {
267  // Check whether all sebs do either best solution search or not
268  bool best;
269  {
270  int b = 0;
271  for (int i=sebs.size(); i--; )
272  b += sebs[i]->best() ? 1 : 0;
273  if ((b > 0) && (b < sebs.size()))
274  throw Search::MixedBest("PBS::PBS");
275  best = (b == sebs.size());
276  }
277 
279  Search::Statistics stat;
280 
281  if (s->status(stat) == SS_FAILED) {
282  stat.fail++;
283  if (!opt.clone)
284  delete s;
285  e = Search::Seq::dead(opt,stat);
286  return;
287  }
288 
289  // Check whether a clone must be used
290  T* master = opt.clone ?
291  dynamic_cast<T*>(s->clone()) : s;
292  opt.clone = false;
293 
294  // Always execute master function
295  (void) master->master(0);
296 
297 #ifdef GECODE_HAS_THREADS
298  if (opt.threads > 1.0)
299  e = Search::pbspar<T,E>(master,sebs,stat,opt,best);
300  else
301 #endif
302  e = Search::pbsseq<T,E>(master,sebs,stat,opt,best);
303  }
304 
305  template<class T, template<class> class E>
306  inline
307  PBS<T,E>::PBS(T* s, SEBs& sebs, const Search::Options& o) {
308  build(s,sebs,o);
309  }
310  template<class T, template<class> class E>
311  inline
312  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1,
313  const Search::Options& o) {
314  SEBs sebs(2, seb0, seb1);
315  build(s,sebs,o);
316  }
317  template<class T, template<class> class E>
318  inline
319  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
320  const Search::Options& o) {
321  SEBs sebs(3, seb0, seb1, seb2);
322  build(s,sebs,o);
323  }
324  template<class T, template<class> class E>
325  inline
326  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
327  const Search::Options& o) {
328  SEBs sebs(4, seb0, seb1, seb2, seb3);
329  build(s,sebs,o);
330  }
331 
332  template<class T, template<class> class E>
333  inline T*
334  pbs(T* s, const Search::Options& o) {
335  PBS<T,E> r(s,o);
336  return r.next();
337  }
338 
339  template<class T, template<class> class E>
340  inline SEB
341  pbs(const Search::Options& o) {
342  return new Search::PbsBuilder<T,E>(o);
343  }
344 
345 }
346 
347 // STATISTICS: search-other
Engine * pbsengine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, const Search::Options &opt, bool best)
Create sequential portfolio engine.
Definition: pbs.cpp:48
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition: pbs.hpp:266
Search engine implementation interface
Definition: search.hh:901
Engine * pbspar(T *master, const Search::Statistics &stat, Options &opt)
Definition: pbs.hpp:157
A PBS engine builder.
Definition: pbs.hpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
Search engine statistics
Definition: search.hh:149
Engine * pbsseq(T *master, const Search::Statistics &stat, Options &opt)
Definition: pbs.hpp:99
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Meta engine using a portfolio of search engines.
Definition: search.hh:1239
#define GECODE_SEARCH_EXPORT
Definition: search.hh:69
Options & options(void)
Provide access to options.
Definition: build.hpp:44
virtual Engine * operator()(Space *s) const
The actual build function.
Definition: pbs.hpp:61
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
Search engine options
Definition: search.hh:748
A class for building search engines.
Definition: search.hh:967
Exception: No assets requested for portfolio-based search
Definition: exception.hpp:52
Options opt
Stored and already expanded options.
Definition: search.hh:970
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition: build.hpp:62
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:50
Engine * dead(const Options &o, const Statistics &stat)
Definition: dead.cpp:94
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
Handle to region.
Definition: region.hpp:57
Engine * pbsengine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, bool best)
Create parallel portfolio engine.
Definition: pbs.cpp:70
Computation spaces.
Definition: core.hpp:1668
Options expand(void) const
Expand with real number of threads.
Definition: options.cpp:47
double threads
Number of threads to use.
Definition: search.hh:753
const bool b
Whether engine to be built is a best solution search engine.
Definition: search.hh:972
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
Stop * pbsstop(Stop *so)
Create stop object.
Definition: pbs.cpp:43
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition: core.cpp:829
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:771
Exception: Mixed non-best and best solution search requested
Definition: exception.hpp:58
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:761
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:334
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
bool best(void) const
Whether engine is a best solution search engine.
Definition: build.hpp:52
PbsBuilder(const Options &opt)
The constructor.
Definition: pbs.hpp:56
Stop * pbsstop(Stop *so)
Create stop object.
Definition: pbs.cpp:65
Passing search engine builder arguments.
Definition: search.hh:1004
Stop * stop
Stop object for stopping search.
Definition: search.hh:767
Gecode toplevel namespace
Space is failed
Definition: core.hpp:1608
Base-class for Stop-object.
Definition: search.hh:801
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition: pbs.hpp:225