40#ifdef GECODE_HAS_EXPERIMENTAL
42#ifdef GECODE_HAS_THREADS
51 std::unique_ptr<Space>
root;
56 bool open(
void)
const override {
57 return !
layer.empty();
73 bool room = (
opt.frontier_limit == 0UL) || (stored <
opt.frontier_limit);
93 std::unique_ptr<Task> t(
new Task);
94 t->expansion.select(std::unique_ptr<Space>(
root->clone()));
104 root.reset(r.clone());
148#ifdef GECODE_HAS_THREADS
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);
169 CABS::initialize(
Space* s,
bool clone) {
174 status = s->
status(*
this);
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);
188 CABS::admit(std::unique_ptr<Space> s,
unsigned long int d) {
189 std::int64_t b = guidance.
bound(*s);
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() +
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) {
210 CABS::publish(std::unique_ptr<Space> s) {
213 std::int64_t
b = guidance.bound(*s);
214 if (!best.improves(b))
216 Space* copy = s->clone();
217 best.update(s.release(),b);
222 CABS::advance(
void) {
223 if (!candidates.empty()) {
224 candidates.release(layer);
225 layer.sort(priority);
228 if (!candidates.improving(best))
230 if (!candidates.widen(opt.max_width)) {
235 expansion.select(std::unique_ptr<Space>(root->clone()));
254 if (layer.empty() && !advance())
257 Entry e = layer.pop();
258 std::unique_ptr<Space> s(e.
space);
259 if (!best.improves(e.
bound)) {
263 expansion.select(std::move(s));
275 if (
Space* s = publish(expansion.take()))
279 if (!best.improves(guidance.bound(expansion.space()))) {
286 best.space.get(),best.revision);
289 switch (step.status) {
294 if (
Space* s = publish(std::move(step.space)))
298 if (!admit(std::move(step.space),depth+1))
319 std::int64_t b = guidance.bound(s);
320 if (best.improves(b))
321 best.update(s.
clone(),b);
326 std::unique_ptr<Space> replacement(s);
335 counted = _limited =
false;
339 (void) replacement.release();
No-goods recorded from restarts.
static NoGoods eng
Empty no-goods.
Candidates for the next layer of CABS.
@ FULL
The entry needs a new slot but there is no room.
Search engine implementation interface
Stack of entries owning their spaces.
Open node of a heuristic search engine.
Space * space
The stable space (owned by the container holding the entry).
unsigned long long int revision
Incumbent revision the space has been constrained with.
unsigned long int depth
Depth of the node.
std::int64_t bound
Bound and rank of the space.
Evaluate bound
Optimistic objective bound (required).
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
unsigned long int frontier_limit
Maximal number of stored nodes for CABS (zero for no limit).
bool clone
Whether engines create a clone when being initialized.
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Options expand(void) const
Expand with real number of threads.
SearchTracer * tracer
Tracer object for tracing search.
double threads
Number of threads to use.
Parallel complete anytime beam search.
Priority priority
Order of nodes in a layer.
std::unique_ptr< Space > root
Root for restarting with a wider beam.
CABS(Space *s, const Options &o)
Initialize for space s with options o.
bool open(void) const override
Whether there are open nodes.
void submit(const Entry &e, bool leased) override
Add child e, or delete it; leased tells whether its parent is still leased.
void clear(void) override
Delete all open nodes.
Entry select(void) override
Remove and return the next open node.
void started(const Space &r) override
Called with the root r when search starts.
Beam candidates
Candidates for the next layer.
bool advance(void) override
Called when all work is done, return whether there is new work.
Entries layer
Nodes of the current layer, preferred node on top.
~CABS(void) override
Destructor.
Node leased by a worker, or partially expanded node.
unsigned long long int order
Number of created entries.
Search::Statistics stat
Statistics.
Options opt
Search options.
void terminate(void)
Stop all workers (must be called by subclass destructors).
bool keyed
Whether to compute dominance keys.
HeuristicGuidance guidance
Guidance.
void initialize(Space *s, bool clone)
Start search from root s.
unsigned int batch
Number of children a worker collects before submitting.
void push(Task *t)
Add pending task t.
bool running
Whether search is running, being shut down, stopped, or limited.
unsigned int n_pending
Number of partially expanded nodes.
unsigned int active
Number of workers holding a task.
Incumbent best
Best solution so far.
static const unsigned int max_batch
Maximal number of children a worker collects before submitting.
Frontier(const Options &o)
Initialize with options o.
Order of open nodes: whether a is preferred to b.
bool limited(void) const override
Whether search stopped at the width or frontier limit.
CABSEngine(Space *s, const Options &o)
Initialize for space s with options o.
Sequential complete anytime beam search.
void constrain(const Space &b)
Constrain future solutions to be better than b.
Space * next(void)
Return next better solution (nullptr if none or stopped).
Statistics statistics(void) const
Return statistics.
bool limited(void) const
Whether search stopped at the width or frontier limit.
NoGoods & nogoods(void)
Return no-goods (none).
CABS(Space *s, const Options &o)
Initialize for space s with options o.
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
unsigned long int restart
Number of restarts.
unsigned long long int fail
Number of failed nodes in search tree.
unsigned long long int node
Number of nodes expanded.
Exception: Missing guidance for heuristic search
Exception: Search engine does not support tracing
WorkerToEngine(Space *s, const Options &o)
bool _stopped
Whether engine has been stopped.
void start(void)
Reset stop information.
bool stop_seq(Options &o)
Check stop and wait for admission of a sequential worker.
void stack_depth(unsigned long int d)
Record stack depth d.
void reset(void)
Reset information.
Space * clone(void) const
Clone space.
SpaceStatus status(StatusStatistics &stat)
Query space status.
@ SS_BRANCH
Space must be branched (at least one brancher left)
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
Engine * cabsengine(Space *s, const Options &o)
Create CABS engine.
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
#define GECODE_NEVER
Assert that this command is never executed.