Generated on Wed Jan 24 2018 21:22:26 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: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
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 <climits>
39 
40 namespace Gecode { namespace Search { namespace Meta { namespace Sequential {
41 
42 
45  : so(so0) {}
46  forceinline void
48  ssi = ssi0;
49  }
50 
51 
52  forceinline void
54  slave = e; stop = s;
55  }
57  Slave::next(void) {
58  return slave->next();
59  }
61  Slave::statistics(void) const {
62  return slave->statistics();
63  }
64  forceinline bool
65  Slave::stopped(void) const {
66  return slave->stopped();
67  }
68  forceinline void
70  slave->constrain(b);
71  }
73  Slave::~Slave(void) {
74  delete slave;
75  delete stop;
76  }
77 
78 
79  template<bool best>
81  PBS<best>::PBS(Engine** e, Stop** s, unsigned int n,
82  const Statistics& stat0,
83  const Search::Options& opt)
84  : stat(stat0), slice(opt.slice),
85  slaves(heap.alloc<Slave>(n)), n_slaves(n), cur(0),
86  slave_stop(false) {
87  ssi.done = false;
88  ssi.l = opt.slice;
89  for (unsigned int i=n; i--; ) {
90  slaves[i].init(e[i],static_cast<PortfolioStop*>(s[i]));
91  static_cast<PortfolioStop*>(s[i])->share(&ssi);
92  }
93  }
94 
95  template<bool best>
96  Space*
98  slave_stop = false;
99  unsigned int n_exhausted = 0;
100  while (n_slaves > 0) {
101  if (Space* s = slaves[cur].next()) {
102  // Constrain other slaves
103  if (best) {
104  for (unsigned int i=0; i<cur; i++)
105  slaves[i].constrain(*s);
106  for (unsigned int i=cur+1; i<n_slaves; i++)
107  slaves[i].constrain(*s);
108  }
109  return s;
110  }
111  if (slaves[cur].stopped()) {
112  if (ssi.done) {
113  cur++; n_exhausted++;
114  } else {
115  slave_stop = true;
116  return NULL;
117  }
118  } else {
119  // This slave is done, kill it after saving the statistics
120  stat += slaves[cur].statistics();
121  slaves[cur].~Slave();
122  slaves[cur] = slaves[--n_slaves];
123  if (n_slaves == 1)
124  // Disable stoping by seeting a high limit
125  ssi.l = ULONG_MAX;
126  }
127  if (n_exhausted == n_slaves) {
128  n_exhausted = 0;
129  // Increment by one slice
130  ssi.l += slice;
131  }
132  if (cur == n_slaves)
133  cur = 0;
134  }
135  return NULL;
136  }
137 
138  template<bool best>
139  bool
140  PBS<best>::stopped(void) const {
141  return slave_stop;
142  }
143 
144  template<bool best>
145  Statistics
146  PBS<best>::statistics(void) const {
147  Statistics s(stat);
148  for (unsigned int i=n_slaves; i--; )
149  s += slaves[i].statistics();
150  return s;
151  }
152 
153  template<bool best>
154  void
156  if (!best)
157  throw NoBest("PBS::constrain");
158  for (unsigned int i=0; i<n_slaves; i++)
159  slaves[i].constrain(b);
160  }
161 
162  template<bool best>
164  for (unsigned int i=n_slaves; i--; )
165  slaves[i].~Slave();
166  // Note that n_slaves might be different now!
167  heap.rfree(slaves);
168  }
169 
170 }}}}
171 
172 // STATISTICS: search-meta
Search engine implementation interface
Definition: search.hh:601
Statistics stat
Master statistics.
Definition: pbs.hh:99
Search engine statistics
Definition: search.hh:140
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
unsigned long int l
The current failure limit, incremented for each slice.
Definition: pbs.hh:51
Search engine options
Definition: search.hh:446
Space * next(void)
Return next solution.
Definition: pbs.hpp:57
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition: search.hh:465
Computation spaces.
Definition: core.hpp:1748
Runnable slave of a portfolio master.
Definition: pbs.hh:71
virtual Statistics statistics(void) const
Return statistics.
Definition: pbs.hpp:146
SharedStopInfo ssi
Shared slave information.
Definition: pbs.hh:101
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Options opt
The options.
Definition: test.cpp:101
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: pbs.hpp:97
unsigned int slice
Size of a slice.
Definition: pbs.hh:103
bool stopped(void) const
Check whether slave has been stopped.
Definition: pbs.hpp:65
void constrain(const Space &b)
Constrain with better solution b.
Definition: pbs.hpp:69
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
PBS(Engine **slaves, Stop **stops, unsigned int n, const Statistics &stat, const Search::Options &opt)
Initialize.
Definition: pbs.hpp:81
unsigned int cur
Current slave to run.
Definition: pbs.hh:109
virtual bool stop(const Statistics &s, const Options &o)
Return true if portfolio engine must be stopped.
Definition: pbs.cpp:43
Stop object used for controling slaves in a portfolio.
Definition: pbs.hh:55
bool done
Whether search stopped because the slice is done.
Definition: pbs.hh:49
void init(Engine *s, Stop *so)
Initialize with slave s and its stop object so.
Definition: pbs.hpp:53
virtual ~PBS(void)
Destructor.
Definition: pbs.hpp:163
Heap heap
The single global heap.
Definition: heap.cpp:48
#define forceinline
Definition: config.hpp:173
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: pbs.hpp:140
Exception: Best solution search is not supported
Definition: exception.hpp:64
~Slave(void)
Delete slave.
Definition: pbs.hpp:73
bool slave_stop
Whether a slave has been stopped.
Definition: pbs.hh:111
Gecode toplevel namespace
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition: pbs.hpp:155
Base-class for Stop-object.
Definition: search.hh:501
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Definition: search.hh:124
void share(SharedStopInfo *ssi)
Intialize shared stop information.
Definition: pbs.hpp:47
unsigned int n_slaves
Number of slave engines.
Definition: pbs.hh:107
Statistics statistics(void) const
Return statistics of slave.
Definition: pbs.hpp:61