Generated on for Gecode by doxygen 1.17.0
cabs.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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
35#include <gecode/search.hh>
39
40#ifdef GECODE_HAS_EXPERIMENTAL
41
42#ifdef GECODE_HAS_THREADS
43namespace Gecode { namespace Search { namespace Par {
44
46 class CABS : public Frontier {
47 protected:
51 std::unique_ptr<Space> root;
56 bool open(void) const override {
57 return !layer.empty();
58 }
59 Entry select(void) override {
60 return layer.pop();
61 }
62 void submit(const Entry& e, bool leased) override {
63 if (!best.improves(e.bound)) {
64 stat.fail++;
65 delete e.space;
66 return;
67 }
68 Entry f = e;
69 f.order = order++;
70 // Every other worker holds a parent and at most one child
71 unsigned long int stored = layer.entries() + candidates.size() +
72 n_pending + 2*(active-1) + (leased ? 1 : 0);
73 bool room = (opt.frontier_limit == 0UL) || (stored < opt.frontier_limit);
74 if (candidates.offer(f,guidance,room) == Beam::FULL) {
75 delete f.space;
76 _limited = _stopped = true;
77 running = false;
78 }
79 }
80 bool advance(void) override {
81 if (!candidates.empty()) {
82 candidates.release(layer);
83 layer.sort(priority);
84 return true;
85 }
86 if (!candidates.improving(best))
87 return false;
88 if (!candidates.widen(opt.max_width)) {
89 _limited = _stopped = true;
90 return false;
91 }
92 stat.restart++;
93 std::unique_ptr<Task> t(new Task);
94 t->expansion.select(std::unique_ptr<Space>(root->clone()));
95 push(t.release());
96 return true;
97 }
98 void clear(void) override {
99 layer.clear();
100 candidates.clear();
101 root.reset();
102 }
103 void started(const Space& r) override {
104 root.reset(r.clone());
105 }
106 public:
108 CABS(Space* s, const Options& o)
109 : Frontier(o), priority{guidance.sense,static_cast<bool>(guidance.rank)},
110 candidates(priority,guidance.dominates && guidance.dominance_key) {
111 batch = (o.frontier_limit == 0UL) ? max_batch : 1;
112 keyed = guidance.dominates && guidance.dominance_key;
113 initialize(s,o.clone);
114 }
115
116 ~CABS(void) override {
117 terminate();
118 }
119 };
120
121}}}
122#endif
123
124namespace Gecode { namespace Search { namespace Seq {
125
127 class CABSEngine : public WorkerToEngine<CABS> {
128 public:
130 CABSEngine(Space* s, const Options& o) : WorkerToEngine<CABS>(s,o) {}
132 bool limited(void) const override {
133 return w.limited();
134 }
135 };
136
137}}}
138
139namespace Gecode { namespace Search {
140
141 Engine*
142 cabsengine(Space* s, const Options& o) {
143 Options e = o.expand();
144 if (e.tracer != nullptr)
145 throw UnsupportedTracer("CABS::CABS");
146 if ((e.guidance == nullptr) || !e.guidance->bound)
147 throw UninitializedGuidance("CABS::CABS");
148#ifdef GECODE_HAS_THREADS
149 if (e.threads > 1.0)
150 return new Par::CABS(s,e);
151#endif
152 return new Seq::CABSEngine(s,e);
153 }
154
155}}
156
157namespace Gecode { namespace Search { namespace Seq {
158
160 : opt(o), guidance(*o.guidance),
161 priority{guidance.sense,static_cast<bool>(guidance.rank)},
162 candidates(priority,guidance.dominates && guidance.dominance_key),
163 order(0), status(SS_FAILED), depth(0), revision(0), counted(false),
164 best(guidance.sense), _limited(false) {
165 initialize(s,o.clone);
166 }
167
168 void
169 CABS::initialize(Space* s, bool clone) {
170 if (s == nullptr) {
171 fail++;
172 return;
173 }
174 status = s->status(*this);
175 if (status == SS_FAILED) {
176 fail++;
177 if (!clone)
178 delete s;
179 return;
180 }
181 // The restart root and the first node are clones of the stable root
182 std::unique_ptr<Space> r(clone ? s->clone() : nullptr);
183 expansion.select(std::unique_ptr<Space>((clone ? r.get() : s)->clone()));
184 root.reset(clone ? r.release() : s);
185 }
186
187 bool
188 CABS::admit(std::unique_ptr<Space> s, unsigned long int d) {
189 std::int64_t b = guidance.bound(*s);
190 if (!best.improves(b)) {
191 fail++;
192 return true;
193 }
194 std::int64_t r = guidance.rank ? guidance.rank(*s) : 0;
195 std::size_t k = (guidance.dominates && guidance.dominance_key) ?
196 guidance.dominance_key(*s) : 0;
197 unsigned long int stored = layer.entries() + candidates.size() +
198 (expansion ? 1 : 0);
199 bool room = (opt.frontier_limit == 0UL) || (stored < opt.frontier_limit);
200 Entry e{s.get(),b,r,k,d,order++,best.revision};
201 if (candidates.offer(e,guidance,room) == Beam::FULL) {
202 _limited = _stopped = true;
203 return false;
204 }
205 (void) s.release();
206 return true;
207 }
208
209 Space*
210 CABS::publish(std::unique_ptr<Space> s) {
211 // Delete exhausted branchers before cloning the solution
212 (void) s->choice();
213 std::int64_t b = guidance.bound(*s);
214 if (!best.improves(b))
215 return nullptr;
216 Space* copy = s->clone();
217 best.update(s.release(),b);
218 return copy;
219 }
220
221 bool
222 CABS::advance(void) {
223 if (!candidates.empty()) {
224 candidates.release(layer);
225 layer.sort(priority);
226 return true;
227 }
228 if (!candidates.improving(best))
229 return false;
230 if (!candidates.widen(opt.max_width)) {
231 _limited = _stopped = true;
232 return false;
233 }
234 restart++;
235 expansion.select(std::unique_ptr<Space>(root->clone()));
236 status = SS_BRANCH;
237 depth = 0;
238 revision = 0;
239 counted = false;
240 return true;
241 }
242
243 Space*
245 if (_limited) {
246 _stopped = true;
247 return nullptr;
248 }
249 start();
250 while (true) {
251 if (stop_seq(opt))
252 return nullptr;
253 if (!expansion) {
254 if (layer.empty() && !advance())
255 return nullptr;
256 if (!expansion) {
257 Entry e = layer.pop();
258 std::unique_ptr<Space> s(e.space);
259 if (!best.improves(e.bound)) {
260 fail++;
261 continue;
262 }
263 expansion.select(std::move(s));
264 depth = e.depth;
265 revision = e.revision;
266 counted = true;
267 }
268 }
269 if (!counted) {
270 // The root of a pass
271 node++;
272 stack_depth(depth);
273 counted = true;
274 if (status == SS_SOLVED) {
275 if (Space* s = publish(expansion.take()))
276 return s;
277 continue;
278 }
279 if (!best.improves(guidance.bound(expansion.space()))) {
280 fail++;
281 expansion.reset();
282 continue;
283 }
284 }
285 ExpansionStep step = expansion.next(*this,depth+1,revision,
286 best.space.get(),best.revision);
287 if (step.state == ExpansionStep::EXHAUSTED)
288 continue;
289 switch (step.status) {
290 case SS_FAILED:
291 fail++;
292 break;
293 case SS_SOLVED:
294 if (Space* s = publish(std::move(step.space)))
295 return s;
296 break;
297 case SS_BRANCH:
298 if (!admit(std::move(step.space),depth+1))
299 return nullptr;
300 break;
301 default:
303 }
304 }
305 }
306
308 CABS::statistics(void) const {
309 return *this;
310 }
311
312 bool
313 CABS::limited(void) const {
314 return _limited;
315 }
316
317 void
319 std::int64_t b = guidance.bound(s);
320 if (best.improves(b))
321 best.update(s.clone(),b);
322 }
323
324 void
326 std::unique_ptr<Space> replacement(s);
327 expansion.reset();
328 layer.clear();
329 candidates.clear();
330 root.reset();
331 best.reset();
332 order = 0;
333 revision = 0;
334 depth = 0;
335 counted = _limited = false;
337 initialize(s,false);
338 // The root is owned by the engine after initialize returns
339 (void) replacement.release();
340 }
341
342 NoGoods&
344 return NoGoods::eng;
345 }
346
347}}}
348
349#endif
350
351// STATISTICS: search-other
No-goods recorded from restarts.
Definition core.hpp:1606
static NoGoods eng
Empty no-goods.
Definition core.hpp:1628
Candidates for the next layer of CABS.
Definition heuristic.hh:172
@ FULL
The entry needs a new slot but there is no room.
Definition heuristic.hh:177
Search engine implementation interface
Definition search.hh:1063
Stack of entries owning their spaces.
Definition heuristic.hh:115
Open node of a heuristic search engine.
Definition heuristic.hh:53
Space * space
The stable space (owned by the container holding the entry).
Definition heuristic.hh:56
unsigned long long int revision
Incumbent revision the space has been constrained with.
Definition heuristic.hh:66
unsigned long int depth
Depth of the node.
Definition heuristic.hh:62
std::int64_t bound
Bound and rank of the space.
Definition heuristic.hh:58
Evaluate bound
Optimistic objective bound (required).
Definition search.hh:1268
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
Definition heuristic.hh:101
Search engine options
Definition search.hh:848
unsigned long int frontier_limit
Maximal number of stored nodes for CABS (zero for no limit).
Definition search.hh:886
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:851
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Definition search.hh:882
Options expand(void) const
Expand with real number of threads.
Definition options.cpp:43
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
double threads
Number of threads to use.
Definition search.hh:853
Parallel complete anytime beam search.
Definition cabs.cpp:46
Priority priority
Order of nodes in a layer.
Definition cabs.cpp:49
std::unique_ptr< Space > root
Root for restarting with a wider beam.
Definition cabs.cpp:51
CABS(Space *s, const Options &o)
Initialize for space s with options o.
Definition cabs.cpp:108
bool open(void) const override
Whether there are open nodes.
Definition cabs.cpp:56
void submit(const Entry &e, bool leased) override
Add child e, or delete it; leased tells whether its parent is still leased.
Definition cabs.cpp:62
void clear(void) override
Delete all open nodes.
Definition cabs.cpp:98
Entry select(void) override
Remove and return the next open node.
Definition cabs.cpp:59
void started(const Space &r) override
Called with the root r when search starts.
Definition cabs.cpp:103
Beam candidates
Candidates for the next layer.
Definition cabs.cpp:55
bool advance(void) override
Called when all work is done, return whether there is new work.
Definition cabs.cpp:80
Entries layer
Nodes of the current layer, preferred node on top.
Definition cabs.cpp:53
~CABS(void) override
Destructor.
Definition cabs.cpp:116
Node leased by a worker, or partially expanded node.
Definition frontier.hh:56
unsigned long long int order
Number of created entries.
Definition frontier.hh:96
Search::Statistics stat
Statistics.
Definition frontier.hh:108
Options opt
Search options.
Definition frontier.hh:88
void terminate(void)
Stop all workers (must be called by subclass destructors).
Definition frontier.cpp:135
bool keyed
Whether to compute dominance keys.
Definition frontier.hh:136
HeuristicGuidance guidance
Guidance.
Definition frontier.hh:90
void initialize(Space *s, bool clone)
Start search from root s.
Definition frontier.cpp:74
unsigned int batch
Number of children a worker collects before submitting.
Definition frontier.hh:134
void push(Task *t)
Add pending task t.
Definition frontier.cpp:69
bool running
Whether search is running, being shut down, stopped, or limited.
Definition frontier.hh:112
unsigned int n_pending
Number of partially expanded nodes.
Definition frontier.hh:100
unsigned int active
Number of workers holding a task.
Definition frontier.hh:110
Incumbent best
Best solution so far.
Definition frontier.hh:92
static const unsigned int max_batch
Maximal number of children a worker collects before submitting.
Definition frontier.hh:132
Frontier(const Options &o)
Initialize with options o.
Definition frontier.cpp:58
Order of open nodes: whether a is preferred to b.
Definition heuristic.hh:70
Sequential CABS engine.
Definition cabs.cpp:127
bool limited(void) const override
Whether search stopped at the width or frontier limit.
Definition cabs.cpp:132
CABSEngine(Space *s, const Options &o)
Initialize for space s with options o.
Definition cabs.cpp:130
Sequential complete anytime beam search.
Definition cabs.hh:46
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition cabs.cpp:318
Space * next(void)
Return next better solution (nullptr if none or stopped).
Definition cabs.cpp:244
Statistics statistics(void) const
Return statistics.
Definition cabs.cpp:308
bool limited(void) const
Whether search stopped at the width or frontier limit.
Definition cabs.cpp:313
NoGoods & nogoods(void)
Return no-goods (none).
Definition cabs.cpp:343
CABS(Space *s, const Options &o)
Initialize for space s with options o.
Definition cabs.cpp:159
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
Search engine statistics
Definition search.hh:155
unsigned long int restart
Number of restarts.
Definition search.hh:164
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
Exception: Missing guidance for heuristic search
Definition exception.hpp:85
Exception: Search engine does not support tracing
Definition exception.hpp:91
WorkerToEngine(Space *s, const Options &o)
Definition support.hh:77
bool _stopped
Whether engine has been stopped.
Definition worker.hh:47
void start(void)
Reset stop information.
Definition worker.hh:76
bool stop_seq(Options &o)
Check stop and wait for admission of a sequential worker.
Definition worker.hh:89
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:114
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
Space * clone(void) const
Clone space.
Definition core.hpp:3384
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Engine * cabsengine(Space *s, const Options &o)
Create CABS engine.
Definition cabs.cpp:142
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
Gecode::IntSet d(v, 7)
const int r[4][2]
Definition dom.cpp:152
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56