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