Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
37namespace 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
65namespace 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
78namespace 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
91namespace 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
109
110 for (unsigned int i=0U; 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
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
165
166 Engine** slaves = r.alloc<Engine*>(n_slaves);
167 Stop** stops = r.alloc<Stop*>(n_slaves);
168
169 for (unsigned int i=0U; 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
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
218namespace Gecode {
219
220 template<class T, template<class> class E>
222 Search::Options opt(o.expand());
223
224 if (opt.assets == 0)
225 throw Search::NoAssets("PBS::PBS");
226
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=0; 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
274 Search::Options opt(o.expand());
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
307 template<class T, template<class> class E>
308 inline T*
309 pbs(T* s, const Search::Options& o) {
310 PBS<T,E> r(s,o);
311 return r.next();
312 }
313
314 template<class T, template<class> class E>
315 inline SEB
317 return new Search::PbsBuilder<T,E>(o);
318 }
319
320}
321
322// STATISTICS: search-other
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
void assets(unsigned int n)
Set default number of assets in a portfolio.
Definition options.hpp:355
void threads(double n)
Set number of parallel threads.
Definition options.hpp:292
Meta engine using a portfolio of search engines.
Definition search.hh:1236
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition pbs.hpp:221
Handle to region.
Definition region.hpp:55
Passing search engine builder arguments.
Definition search.hh:1002
@ PBS
Engine is a PBS engine.
Definition search.hh:198
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
Definition build.hpp:58
A class for building search engines.
Definition search.hh:965
Options opt
Stored and already expanded options.
Definition search.hh:968
Search engine implementation interface
Definition search.hh:899
Exception: Mixed non-best and best solution search requested
Definition exception.hpp:54
Exception: No assets requested for portfolio-based search
Definition exception.hpp:48
Search engine options
Definition search.hh:746
Options expand(void) const
Expand with real number of threads.
Definition options.cpp:43
Stop * stop
Stop object for stopping search.
Definition search.hh:765
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:769
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:759
double threads
Number of threads to use.
Definition search.hh:751
A PBS engine builder.
Definition pbs.hpp:41
PbsBuilder(const Options &opt)
The constructor.
Definition pbs.hpp:52
virtual Engine * operator()(Space *s) const
The actual build function.
Definition pbs.hpp:57
Search engine statistics
Definition search.hh:147
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Base-class for Stop-object.
Definition search.hh:799
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1742
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:863
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:309
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Engine * pbsengine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, bool best)
Create parallel portfolio engine.
Definition pbs.cpp:66
Stop * pbsstop(Stop *so)
Create stop object.
Definition pbs.cpp:61
Engine * dead(const Options &o, const Statistics &stat)
Definition dead.cpp:90
Stop * pbsstop(Stop *so)
Create stop object.
Definition pbs.cpp:39
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
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition build.hpp:58
Engine * pbspar(T *master, const Search::Statistics &stat, Options &opt)
Definition pbs.hpp:153
Engine * pbsseq(T *master, const Search::Statistics &stat, Options &opt)
Definition pbs.hpp:95
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
Definition search.hh:993
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
#define GECODE_SEARCH_EXPORT
Definition search.hh:67