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 <climits>
39 
40 namespace Gecode { namespace Search { namespace Seq {
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 
90  for (unsigned int i=n; i--; ) {
91  slaves[i].init(e[i],static_cast<PortfolioStop*>(s[i]));
92  static_cast<PortfolioStop*>(s[i])->share(&ssi);
93  }
94  }
95 
96  template<bool best>
97  Space*
99  slave_stop = false;
100  unsigned int n_exhausted = 0;
101  while (n_slaves > 0) {
102  if (Space* s = slaves[cur].next()) {
103  // Constrain other slaves
104  if (best) {
105  for (unsigned int i=0; i<cur; i++)
106  slaves[i].constrain(*s);
107  for (unsigned int i=cur+1; i<n_slaves; i++)
108  slaves[i].constrain(*s);
109  }
110  return s;
111  }
112  if (slaves[cur].stopped()) {
113  if (ssi.done) {
114  cur++; n_exhausted++;
115  } else {
116  slave_stop = true;
117  return NULL;
118  }
119  } else {
120  // This slave is done, kill it after saving the statistics
121  stat += slaves[cur].statistics();
122  slaves[cur].~Slave();
123  slaves[cur] = slaves[--n_slaves];
124  if (n_slaves == 1)
125  // Disable stoping by seeting a high limit
126  ssi.l = ULONG_MAX;
127  }
128  if (n_exhausted == n_slaves) {
129  n_exhausted = 0;
130  // Increment by one slice
131  ssi.l += slice;
132  }
133  if (cur == n_slaves)
134  cur = 0;
135  }
136  return NULL;
137  }
138 
139  template<bool best>
140  bool
141  PBS<best>::stopped(void) const {
142  return slave_stop;
143  }
144 
145  template<bool best>
146  Statistics
147  PBS<best>::statistics(void) const {
148  Statistics s(stat);
149  for (unsigned int i=n_slaves; i--; )
150  s += slaves[i].statistics();
151  return s;
152  }
153 
154  template<bool best>
155  void
157  if (!best)
158  throw NoBest("PBS::constrain");
159  for (unsigned int i=0; i<n_slaves; i++)
160  slaves[i].constrain(b);
161  }
162 
163  template<bool best>
165  for (unsigned int i=n_slaves; i--; )
166  slaves[i].~Slave();
167  // Note that n_slaves might be different now!
168  heap.rfree(slaves);
169  }
170 
171 }}}
172 
173 // STATISTICS: search-seq
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition: pbs.hpp:156
Slave * slaves
Slaves.
Definition: pbs.hh:105
PortfolioStop(Stop *so)
Initialize.
Definition: pbs.hpp:44
Search engine implementation interface
Definition: search.hh:901
Search engine statistics
Definition: search.hh:149
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
Search engine options
Definition: search.hh:748
~Slave(void)
Delete slave.
Definition: pbs.hpp:73
unsigned int n_slaves
Number of slave engines.
Definition: pbs.hh:107
unsigned int slice
Size of a slice in a portfolio (in number of failures)
Definition: search.hh:763
#define forceinline
Definition: config.hpp:182
PBS(Engine **slaves, Stop **stops, unsigned int n, const Statistics &stat, const Search::Options &opt)
Initialize.
Definition: pbs.hpp:81
Computation spaces.
Definition: core.hpp:1668
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: pbs.hpp:141
Stop object used for controling slaves in a portfolio.
Definition: pbs.hh:55
unsigned int slice
Size of a slice.
Definition: pbs.hh:103
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 Statistics statistics(void) const
Return statistics.
Definition: pbs.hpp:147
Runnable slave of a portfolio master.
Definition: pbs.hh:71
virtual bool stop(const Statistics &s, const Options &o)
Return true if portfolio engine must be stopped.
Definition: pbs.cpp:43
void constrain(const Space &b)
Constrain with better solution b.
Definition: pbs.hpp:69
Statistics statistics(void) const
Return statistics of slave.
Definition: pbs.hpp:61
Space * next(void)
Return next solution.
Definition: pbs.hpp:57
SharedStopInfo ssi
Shared slave information.
Definition: pbs.hh:101
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
bool slave_stop
Whether a slave has been stopped.
Definition: pbs.hh:111
virtual ~PBS(void)
Destructor.
Definition: pbs.hpp:164
void share(SharedStopInfo *ssi)
Intialize shared stop information.
Definition: pbs.hpp:47
Heap heap
The single global heap.
Definition: heap.cpp:48
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
Statistics stat
Master statistics.
Definition: pbs.hh:99
Shared stop information.
Definition: pbs.hh:46
Exception: Best solution search is not supported
Definition: exception.hpp:64
Gecode toplevel namespace
unsigned int cur
Current slave to run.
Definition: pbs.hh:109
Base-class for Stop-object.
Definition: search.hh:801
unsigned long int l
The current failure limit, incremented for each slice.
Definition: pbs.hh:51
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: pbs.hpp:98
bool stopped(void) const
Check whether slave has been stopped.
Definition: pbs.hpp:65
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Definition: search.hh:130