Generated on for Gecode by doxygen 1.17.0
rbs.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
8 *
9 * Copyright:
10 * Guido Tack, 2012
11 * Mikael Zayenz Lagerkvist, 2026
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
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
40
41namespace Gecode { namespace Search { namespace Seq {
42
43 bool
44 RestartStop::stop(const Statistics& s, const Options& o) {
45 Support::Lock lock(m);
46 // Stop if the fail limit for the engine says so
47 if (s.fail > l) {
48 if (!e_stopped)
49 m_stat.restart++;
50 e_stopped = true;
51 return true;
52 }
53 // Stop if the stop object for the meta engine says so
54 if ((m_stop != nullptr) && m_stop->stop(m_stat+s,o)) {
55 e_stopped = false;
56 return true;
57 }
58 return false;
59 }
60
61 bool
63 Support::Lock lock(m);
64 return (m_stop != nullptr) && m_stop->stop(m_stat+s,o);
65 }
66
67 NoGoods&
69 // The no-goods of an incomplete slave search only hold in its restricted
70 // search space, not in the master.
71 if (!nogoods_valid)
72 return NoGoods::eng;
73 NoGoods& ng = e->nogoods();
74 // Reset number of no-goods found
75 ng.ng(0);
76 return ng;
77 }
78
79 Space*
80 RBS::next(void) {
81 // A failed master proves that no further solution exists
82 if (master == nullptr)
83 return nullptr;
84 m_stopped = false;
85 if (restart) {
86 restart = false;
87 sslr++;
88 NoGoods& ng = master_nogoods();
89 MetaInfo mi(stop->restarts(),MetaInfo::RR_SOL,sslr,e->statistics().fail,last,ng);
90 bool r = master->master(mi);
91 stop->nogood(ng.ng());
92 if (stop->status(master) == SS_FAILED) {
93 stop->update(e->statistics());
94 delete master;
95 master = nullptr;
96 e->reset(nullptr);
97 return nullptr;
98 } else if (r) {
99 stop->update(e->statistics());
100 Space* slave = master;
101 master = master->clone();
102 complete = slave->slave(mi);
104 e->reset(slave);
105 sslr = 0;
106 stop->restart();
107 }
108 }
109 while (true) {
110 Space* n = e->next();
111 if (n != nullptr) {
112 // The engine found a solution
113 restart = true;
114 delete last;
115 last = n->clone();
116 return n;
117 } else if ( (!complete && !e->stopped()) ||
118 (e->stopped() && stop->enginestopped()) ) {
119 // The engine must perform a true restart
120 // The number of the restart has been incremented in the stop object
121 if (!complete && !e->stopped()) {
122 /*
123 * The engine might not have checked its stop object, for example
124 * when the slave failed at the root or a parallel engine had no
125 * work. Without this check, the restarts might never stop.
126 */
127 if (stop->meta_stop(e->statistics(),m_opt)) {
128 m_stopped = true;
129 return nullptr;
130 }
131 stop->restart();
132 }
133 sslr = 0;
134 NoGoods& ng = master_nogoods();
135 MetaInfo mi(stop->restarts(),e->stopped() ? MetaInfo::RR_LIM : MetaInfo::RR_CMPL,sslr,e->statistics().fail,last,ng);
136 (void) master->master(mi);
137 stop->nogood(ng.ng());
138 unsigned long long int nl = ++(*co);
139 stop->limit(e->statistics(),nl);
140 if (stop->status(master) == SS_FAILED) {
141 // The statistics of the engine have been added by limit()
142 delete master;
143 master = nullptr;
144 e->reset(nullptr);
145 return nullptr;
146 }
147 Space* slave = master;
148 master = master->clone();
149 complete = slave->slave(mi);
151 e->reset(slave);
152 } else {
153 return nullptr;
154 }
155 }
157 return nullptr;
158 }
159
161 RBS::statistics(void) const {
162 return stop->metastatistics()+e->statistics();
163 }
164
165 void
167 if (!best)
168 throw NoBest("RBS::constrain");
169 if (master == nullptr)
170 return;
171 if (last != nullptr) {
172 last->constrain(b);
173 if (last->status() == SS_FAILED) {
174 delete last;
175 } else {
176 return;
177 }
178 }
179 last = b.clone();
180 master->constrain(b);
181 e->constrain(b);
182 }
183
184 bool
185 RBS::stopped(void) const {
186 /*
187 * What might happen during parallel search is that the
188 * engine has been stopped but the meta engine has not, so
189 * the meta engine does not perform a restart. However the
190 * invocation of next will do so and no restart will be
191 * missed.
192 *
193 * The engine may still report a stop when the master failed during a
194 * restart after a limit. A failed master is a proof, not a stop.
195 */
196 return (master != nullptr) && (m_stopped || e->stopped());
197 }
198
199 RBS::~RBS(void) {
200 delete e;
201 delete master;
202 delete last;
203 delete co;
204 delete stop;
205 }
206
207}}}
208
209// STATISTICS: search-seq
Information passed by meta search engines.
Definition core.hpp:1635
@ RR_SOL
Restarting after a solution is found.
Definition core.hpp:1651
@ RR_CMPL
Restarting after exhausting search space.
Definition core.hpp:1653
@ RR_LIM
Restarting after reaching restart limit.
Definition core.hpp:1655
No-goods recorded from restarts.
Definition core.hpp:1606
static NoGoods eng
Empty no-goods.
Definition core.hpp:1628
unsigned long int ng(void) const
Return number of no-goods posted.
Definition core.hpp:3204
Exception: Best solution search is not supported
Definition exception.hpp:60
Search engine options
Definition search.hh:848
RestartStop * stop
The stop control object.
Definition rbs.hh:99
virtual Space * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition rbs.cpp:80
bool best
Whether the engine performs best solution search.
Definition rbs.hh:111
Space * master
The master space to restart from.
Definition rbs.hh:93
bool restart
Whether a restart must be performed when next is called.
Definition rbs.hh:109
bool complete
Whether search for the next solution will be complete.
Definition rbs.hh:105
Engine * e
The actual engine.
Definition rbs.hh:91
NoGoods & master_nogoods(void)
Return the no-goods of the last slave search, valid in the master.
Definition rbs.cpp:68
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition rbs.cpp:185
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition rbs.cpp:166
Space * last
The last solution space (possibly nullptr).
Definition rbs.hh:95
Options m_opt
The options for the stop object of the meta engine.
Definition rbs.hh:101
unsigned long int sslr
How many solutions since the last restart.
Definition rbs.hh:103
bool m_stopped
Whether the stop object for the meta engine stopped a restart.
Definition rbs.hh:113
Cutoff * co
The cutoff object.
Definition rbs.hh:97
virtual ~RBS(void)
Destructor.
Definition rbs.cpp:199
bool nogoods_valid
Whether the no-goods of the current slave search hold in the master.
Definition rbs.hh:107
virtual Statistics statistics(void) const
Return statistics.
Definition rbs.cpp:161
bool meta_stop(const Statistics &s, const Options &o)
Return true if the stop object for the meta engine says so.
Definition rbs.cpp:62
virtual bool stop(const Statistics &s, const Options &o)
Return true if meta engine must be stopped.
Definition rbs.cpp:44
Search engine statistics
Definition search.hh:155
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
Computation spaces.
Definition core.hpp:1787
A lock as a scoped frontend for a mutex.
Definition thread.hpp:114
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:918
Space * clone(void) const
Clone space.
Definition core.hpp:3384
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Gecode toplevel namespace
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56