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 <climits>
35
36namespace 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 }
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
67 }
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>
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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
Search engine implementation interface
Definition search.hh:899
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception)
Definition engine.cpp:39
virtual Statistics statistics(void) const =0
Return statistics.
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
virtual bool stopped(void) const =0
Check whether engine has been stopped.
Exception: Best solution search is not supported
Definition exception.hpp:60
Search engine options
Definition search.hh:746
Slave * slaves
Slaves.
Definition pbs.hh:101
SharedStopInfo ssi
Shared slave information.
Definition pbs.hh:97
virtual ~PBS(void)
Destructor.
Definition pbs.hpp:160
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition pbs.hpp:94
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:137
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:143
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:152
PBS(Engine **slaves, Stop **stops, unsigned int n, const Statistics &stat, const Search::Options &opt)
Initialize.
Definition pbs.hpp:77
Stop object used for controling slaves in a portfolio.
Definition pbs.hh:51
void share(SharedStopInfo *ssi)
Intialize shared stop information.
Definition pbs.hpp:43
PortfolioStop(Stop *so)
Initialize.
Definition pbs.hpp:40
Shared stop information.
Definition pbs.hh:42
unsigned long int l
The current failure limit, incremented for each slice.
Definition pbs.hh:47
bool done
Whether search stopped because the slice is done.
Definition pbs.hh:45
Runnable slave of a portfolio master.
Definition pbs.hh:67
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:61
Space * next(void)
Return next solution.
Definition pbs.hpp:53
Engine * slave
The slave engine.
Definition pbs.hh:70
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:65
Stop * stop
Stop object.
Definition pbs.hh:72
void init(Engine *s, Stop *so)
Initialize with slave s and its stop object so.
Definition pbs.hpp:49
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:57
~Slave(void)
Delete slave.
Definition pbs.hpp:69
Search engine statistics
Definition search.hh:147
Base-class for Stop-object.
Definition search.hh:799
Computation spaces.
Definition core.hpp:1742
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187