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