Generated on for Gecode by doxygen 1.17.0
search.cpp
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.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
8 *
9 * Copyright:
10 * Christian Schulte, 2008
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#include <gecode/minimodel.hh>
39#include <gecode/search.hh>
41
42#include "test/test.hh"
43
44#include <atomic>
45#include <chrono>
46#include <future>
47#include <limits>
48#include <memory>
49#include <thread>
50#include <type_traits>
51#include <vector>
52
53static_assert(std::is_copy_constructible<Gecode::NoGoods>::value,
54 "NoGoods must remain copy constructible");
55static_assert(std::is_copy_assignable<Gecode::NoGoods>::value,
56 "NoGoods must remain copy assignable");
57static_assert(std::is_copy_constructible<Gecode::Search::NodeStop>::value,
58 "NodeStop must remain copy constructible");
59static_assert(std::is_copy_assignable<Gecode::Search::NodeStop>::value,
60 "NodeStop must remain copy assignable");
61static_assert(std::is_copy_constructible<Gecode::Search::FailStop>::value,
62 "FailStop must remain copy constructible");
63static_assert(std::is_copy_assignable<Gecode::Search::FailStop>::value,
64 "FailStop must remain copy assignable");
65static_assert(std::is_copy_constructible<Gecode::Search::TimeStop>::value,
66 "TimeStop must remain copy constructible");
67static_assert(std::is_copy_assignable<Gecode::Search::TimeStop>::value,
68 "TimeStop must remain copy assignable");
69static_assert(std::is_copy_constructible<Gecode::Search::RestartStop>::value,
70 "RestartStop must remain copy constructible");
71static_assert(std::is_copy_assignable<Gecode::Search::RestartStop>::value,
72 "RestartStop must remain copy assignable");
73static_assert(
74 std::is_copy_constructible<Gecode::Search::WorkerControl>::value,
75 "WorkerControl must remain copy constructible");
76static_assert(
77 std::is_copy_assignable<Gecode::Search::WorkerControl>::value,
78 "WorkerControl must remain copy assignable");
79
80namespace Test {
81
83 namespace Search {
84
85 using namespace Gecode;
86 using namespace Gecode::Int;
87
88#ifdef GECODE_HAS_EXPERIMENTAL
90 class TreeSpace : public Space {
91 public:
93 struct Node {
95 std::vector<int> children;
96 };
97 typedef std::vector<Node> Graph;
98 std::shared_ptr<const Graph> graph;
102 class Decisions : public Brancher {
103 class Decision : public Choice {
104 public:
105 int vertex;
106 Decision(const Brancher& b, int v, unsigned int n)
107 : Choice(b,n), vertex(v) {}
108 void archive(Archive& e) const override {
109 Choice::archive(e); e << vertex << alternatives();
110 }
111 };
112 public:
113 Decisions(Home home) : Brancher(home) {}
114 Decisions(Space& home, Decisions& b) : Brancher(home,b) {}
115 bool status(const Space& s) const override {
116 return !static_cast<const TreeSpace&>(s).node().children.empty();
117 }
118 const Choice* choice(Space& s) override {
119 const TreeSpace& t = static_cast<const TreeSpace&>(s);
120 return new Decision(*this,t.vertex,
121 static_cast<unsigned int>(t.node().children.size()));
122 }
123 const Choice* choice(const Space&, Archive& e) override {
124 int v; unsigned int n; e >> v >> n;
125 return new Decision(*this,v,n);
126 }
127 ExecStatus commit(Space& s, const Choice& c, unsigned int a) override {
128 TreeSpace& t = static_cast<TreeSpace&>(s);
129 t.vertex = (*t.graph)[static_cast<const Decision&>(c).vertex].children[a];
130 return t.node().cost >= t.ceiling ? ES_FAILED : ES_OK;
131 }
132 Actor* copy(Space& home) override {
133 return new (home) Decisions(home,*this);
134 }
135 size_t dispose(Space& home) override {
136 (void) Brancher::dispose(home);
137 return sizeof(*this);
138 }
139 };
140 TreeSpace(std::shared_ptr<const Graph> g, bool max)
141 : graph(g), maximize(max), vertex(0),
142 ceiling(std::numeric_limits<int>::max()) {
143 (void) new (*this) Decisions(*this);
144 }
148 Space* copy(void) override { return new TreeSpace(*this); }
149 bool master(const MetaInfo&) override { return true; }
150 const Node& node(void) const { return (*graph)[vertex]; }
151 void constrain(const Space& s) override {
152 ceiling = static_cast<const TreeSpace&>(s).node().cost;
153 if (node().cost >= ceiling) fail();
154 }
155
157 guidance(bool max, bool ranked, bool dominance, bool keyed) {
159 HeuristicGuidance g(max ? HeuristicGuidance::MAXIMIZE :
160 HeuristicGuidance::MINIMIZE,
161 [](const Space& s) -> std::int64_t {
162 const TreeSpace& t = static_cast<const TreeSpace&>(s);
163 return t.maximize ? -t.node().bound : t.node().bound;
164 });
165 if (ranked)
166 g.rank = [](const Space& s) -> std::int64_t {
167 return static_cast<const TreeSpace&>(s).node().rank;
168 };
169 if (dominance)
170 g.dominates = [](const Space& a, const Space& b) {
171 return static_cast<const TreeSpace&>(a).node().best <=
172 static_cast<const TreeSpace&>(b).node().best;
173 };
174 if (keyed)
175 g.dominance_key = [](const Space& s) -> std::size_t {
176 return static_cast<std::size_t>
177 (static_cast<const TreeSpace&>(s).node().best % 3);
178 };
179 return g;
180 }
181
182 static std::shared_ptr<const Graph>
184 Graph g;
185 g.push_back({0,0,0,0,{}});
186 grow(g,0,0,d,r);
187 return std::make_shared<const Graph>(std::move(g));
188 }
189 private:
190 static void grow(Graph& g, int v, int depth, int d,
192 if ((depth < d) || ((depth < 5) && (r(4U) != 0U))) {
193 unsigned int n = (depth < d ? 2U : 1U) + r(3U);
194 for (unsigned int i=0; i<n; i++) {
195 int c = static_cast<int>(g.size());
196 g.push_back({g[v].cost+static_cast<int>(r(5U)),0,
197 static_cast<int>(r(10U)),0,{}});
198 g[v].children.push_back(c);
199 grow(g,c,depth+1,d,r);
200 }
201 }
202 if (g[v].children.empty()) {
203 g[v].best = g[v].bound = g[v].cost;
204 } else {
205 g[v].best = std::numeric_limits<int>::max();
206 for (int c : g[v].children)
207 g[v].best = std::min(g[v].best,g[c].best);
208 g[v].bound = g[v].cost +
209 static_cast<int>(r(static_cast<unsigned int>(g[v].best-g[v].cost+1)));
210 }
211 }
212 };
213
216 unsigned long long int limit, step;
217 public:
218 unsigned int stops;
219 Increasing(unsigned long long int s) : limit(s), step(s), stops(0) {}
221 const Gecode::Search::Options&) override {
222 if (s.node <= limit)
223 return false;
224 limit += step;
225 stops++;
226 return true;
227 }
228 };
229
231 template<class Engine>
232 static bool improving(Engine& e, const TreeSpace& root,
233 const Increasing* stop=nullptr) {
234 int last = std::numeric_limits<int>::max();
235 unsigned int stops = 0;
236 while (true) {
237 if (TreeSpace* s = e.next()) {
238 int cost = s->node().cost;
239 delete s;
240 if (cost >= last)
241 return false;
242 last = cost;
243 } else if ((stop != nullptr) && (stop->stops != stops)) {
244 // Resume after the stop object stopped search
245 stops = stop->stops;
246 } else {
247 break;
248 }
249 }
250 return e.stopped() || (last == (*root.graph)[0].best);
251 }
252
254 template<template<class> class E>
255 class Heuristic : public Base {
256 public:
257 Heuristic(const std::string& name)
258 : Base("Search::"+name,TestTags::check()) {}
259 bool run(void) override {
260 for (bool max : {false,true})
261 for (bool ranked : {false,true})
262 for (bool dominance : {false,true})
263 for (unsigned int threads : {1U,2U,4U})
264 for (unsigned int step : {0U,1U,7U}) {
265#ifndef GECODE_HAS_THREADS
266 if (threads > 1U) continue;
267#endif
270 TreeSpace::guidance(max,ranked,dominance,_rand(2U) == 0U);
271 Increasing stop(step);
273 o.threads = threads;
274 o.guidance = &g;
275 if (step > 0U)
276 o.stop = &stop;
277 if (_rand(3U) == 0U)
278 o.max_width = 1UL << _rand(3U);
279 E<TreeSpace> e(&root,o);
280 if (!improving(e,root,step > 0U ? &stop : nullptr))
281 return false;
282 if ((o.max_width == 0UL) && e.stopped())
283 return false;
284 }
285 return true;
286 }
287 };
288
291
293 class HeuristicPortfolio : public Base {
295 class Slow : public Gecode::Search::Stop {
296 public:
297 bool stop(const Gecode::Search::Statistics&,
298 const Gecode::Search::Options&) override {
299 std::this_thread::sleep_for(std::chrono::microseconds(200));
300 return false;
301 }
302 };
303 public:
305 : Base("Search::Heuristic::Portfolio",TestTags::check()) {}
306 bool run(void) override {
307 TreeSpace root(TreeSpace::random(_rand),false);
309 TreeSpace::guidance(false,true,false,false);
311 a.threads = 1;
312 a.guidance = &g;
314 cabs<TreeSpace>(a)});
316#ifdef GECODE_HAS_THREADS
317 o.threads = 3;
318#endif
319 PBS<TreeSpace,BAB> e(&root,assets,o);
320 if (!improving(e,root))
321 return false;
322 // A CABS asset stopping at its width limit must not stop the others
323 return limited(1) && limited(2);
324 }
325
326 static bool limited(unsigned int threads) {
327#ifndef GECODE_HAS_THREADS
328 if (threads > 1U)
329 return true;
330#endif
331 // CABS with width one follows the preferred branch to cost 5
332 TreeSpace::Graph g = {
333 {0,0,0,1,{1,2}}, {0,0,0,5,{3}}, {0,0,1,1,{4}},
334 {5,5,0,5,{}}, {1,1,0,1,{}}
335 };
336 TreeSpace root(std::make_shared<const TreeSpace::Graph>(g),false);
338 TreeSpace::guidance(false,true,false,false);
340 c.threads = 1;
341 c.guidance = &h;
342 c.max_width = 1;
343 // Slow down BAB so that CABS stops first
344 Slow slow;
346 b.threads = 1;
347 b.stop = &slow;
348 SEBs assets({cabs<TreeSpace>(c),bab<TreeSpace>(b)});
350 o.threads = threads;
351 PBS<TreeSpace,BAB> e(&root,assets,o);
352 int last = std::numeric_limits<int>::max();
353 while (TreeSpace* s = e.next()) {
354 last = s->node().cost;
355 delete s;
356 }
357 return (last == 1) && e.stopped();
358 }
360#endif
361
362
370
379
386
388 class TestSpace : public Space {
389 public:
391 TestSpace(void) {}
395 virtual int solutions(void) const = 0;
397 virtual bool best(void) const = 0;
399 virtual bool master(const MetaInfo& mi) {
400 if (mi.type() == MetaInfo::RESTART) {
401 if (mi.last() != nullptr)
402 constrain(*mi.last());
403 return false;
404 } else {
405 return false;
406 }
407 }
408 };
409
411 class FailImmediate : public TestSpace {
412 public:
418 : x(*this,1,0,0) {
419 rel(*this, x[0], IRT_EQ, 1);
420 }
421
423 x.update(*this, s.x);
424 }
425
426 virtual Space* copy(void) {
427 return new FailImmediate(*this);
428 }
429
430 virtual void constrain(const Space&) {
431 }
432
433 virtual int solutions(void) const {
434 return 0;
435 }
436
437 virtual bool best(void) const {
438 return false;
439 }
440
441 static std::string name(void) {
442 return "Fail";
443 }
444 };
445
447 class SolveImmediate : public TestSpace {
448 public:
455
457 x.update(*this, s.x);
458 }
459
460 virtual Space* copy(void) {
461 return new SolveImmediate(*this);
462 }
463
464 virtual void constrain(const Space&) {
465 fail();
466 }
467
468 virtual int solutions(void) const {
469 return 1;
470 }
471
472 virtual bool best(void) const {
473 return true;
474 }
475
476 static std::string name(void) {
477 return "Solve";
478 }
479 };
480
482 class HasSolutions : public TestSpace {
483 public:
491 void branch(const IntVarArgs& x, HowToBranch htb) {
492 switch (htb) {
493 case HTB_NONE:
494 break;
495 case HTB_UNARY:
496 assign(*this, x, INT_ASSIGN_MIN());
497 break;
498 case HTB_BINARY:
500 break;
501 case HTB_NARY:
503 break;
504 }
505 }
506
509 : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
510 distinct(*this, x);
511 rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
512 rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
513 IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
514 IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
515 IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
516 }
517
519 : TestSpace(s),
520 htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
521 x.update(*this, s.x);
522 }
523
524 virtual Space* copy(void) {
525 return new HasSolutions(*this);
526 }
527
528 virtual void constrain(const Space& _s) {
529 const HasSolutions& s = static_cast<const HasSolutions&>(_s);
530 switch (htc) {
531 case HTC_NONE:
532 break;
533 case HTC_LEX_LE:
534 case HTC_LEX_GR:
535 {
536 IntVarArgs y(6);
537 for (int i=0; i<6; i++)
538 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
539 lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
540 break;
541 }
542 case HTC_BAL_LE:
543 case HTC_BAL_GR:
544 {
545 IntVarArgs y(6);
546 for (int i=0; i<6; i++)
547 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
548 IntVar xs(*this, -18, 18);
549 IntVar ys(*this, -18, 18);
550 rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
551 rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
552 rel(*this,
553 expr(*this,abs(xs)),
554 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
555 expr(*this,abs(ys)));
556 break;
557 }
558 }
559 }
560
561 virtual int solutions(void) const {
562 if (htb1 == HTB_NONE) {
563 assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
564 return 1;
565 }
566 if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
567 return 0;
568 if (htb3 == HTB_UNARY)
569 return 4;
570 return 8;
571 }
572
573 virtual bool best(void) const {
574 if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
575 (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
576 return true;
577 switch (htc) {
578 case HTC_NONE:
579 return true;
580 case HTC_LEX_LE:
581 return ((x[0].val()==4) && (x[1].val()==5) &&
582 (x[2].val()==2) && (x[3].val()==3) &&
583 (x[4].val()==0) && (x[5].val()==1));
584 case HTC_LEX_GR:
585 return ((x[0].val()==5) && (x[1].val()==4) &&
586 (x[2].val()==3) && (x[3].val()==2) &&
587 (x[4].val()==1) && (x[5].val()==0));
588 case HTC_BAL_LE:
589 return ((x[0].val()==4) && (x[1].val()==5) &&
590 (x[2].val()==2) && (x[3].val()==3) &&
591 (x[4].val()==0) && (x[5].val()==1));
592 case HTC_BAL_GR:
593 return ((x[0].val()==4) && (x[1].val()==5) &&
594 (x[2].val()==3) && (x[3].val()==2) &&
595 (x[4].val()==0) && (x[5].val()==1));
596 default: GECODE_NEVER;
597 }
598 return false;
599 }
600
601 static std::string name(void) {
602 return "Sol";
603 }
604
605 virtual bool master(const MetaInfo& mi) {
606 switch (mi.type()) {
608 if (mi.last() != nullptr) {
609 const HasSolutions* s
610 = static_cast<const HasSolutions*>(mi.last());
611 BoolVarArgs b;
612 for (int i=0; i<x.size(); i++)
613 b << expr(*this, x[i] == s->x[i]);
614 rel(*this, BOT_AND, b, 0);
615 }
616 break;
618 // Do not kill the brancher!
619 break;
620 default:
621 break;
622 }
623 return false;
624 }
625 };
626
628 class Test : public Base {
629 public:
635 static std::string str(unsigned int i) {
636 std::stringstream s;
637 s << i;
638 return s.str();
639 }
640
641 static std::string str(HowToBranch htb) {
642 switch (htb) {
643 case HTB_NONE: return "None";
644 case HTB_UNARY: return "Unary";
645 case HTB_BINARY: return "Binary";
646 case HTB_NARY: return "Nary";
647 default: GECODE_NEVER;
648 }
650 return "";
651 }
652
653 static std::string str(HowToConstrain htc) {
654 switch (htc) {
655 case HTC_NONE: return "None";
656 case HTC_LEX_LE: return "LexLe";
657 case HTC_LEX_GR: return "LexGr";
658 case HTC_BAL_LE: return "BalLe";
659 case HTC_BAL_GR: return "BalGr";
660 default: GECODE_NEVER;
661 }
663 return "";
664 }
665
666 Test(TestTags tags, const std::string& s,
667 HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
669 : Base("Search::"+s,tags),
670 htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
671
672 Test(const std::string& s,
673 HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
675 : Test(TestTags::standard(),s,_htb1,_htb2,_htb3,_htc) {}
676 };
677
679 static unsigned int
680 worker_capacity(unsigned int threads) {
681#ifdef GECODE_HAS_THREADS
682 return threads;
683#else
684 (void) threads;
685 return 1U;
686#endif
687 }
688
691 int& live;
692 public:
696 ++live;
697 }
698 Space* copy(void) override { return new PortfolioSeed(*this); }
699 ~PortfolioSeed(void) override { --live; }
700 };
701
702 template<class T>
704
707 bool worker_control_failure(unsigned int threads, bool clone,
708 bool restart, bool in_use) {
709 Gecode::Search::WorkerControl control(in_use ? 1U :
710 worker_capacity(threads)+1U);
712 std::unique_ptr<Gecode::DFS<SolveImmediate>> binding;
713 if (in_use) {
715 bound.worker_control = control;
716 binding.reset(new Gecode::DFS<SolveImmediate>(&binding_root,bound));
717 }
718 int live = 0;
719 std::unique_ptr<PortfolioSeed> root(new PortfolioSeed(live));
720 PortfolioSeed* seed = root.get();
721 if (!clone)
722 root.release();
724 o.assets = 1;
725 o.threads = threads;
726 o.clone = clone;
727 o.worker_control = control;
728 std::unique_ptr<Gecode::Search::Cutoff>
730 o.cutoff = cutoff.get();
731 bool caught = false;
732 try {
733 if (restart) {
734 Gecode::RBS<PortfolioSeed> engine(seed,o);
735 cutoff.release();
736 } else {
737 Gecode::PBS<PortfolioSeed> engine(seed,o);
738 }
739 } catch (const Gecode::Search::WorkerControlInUse&) {
740 caught = in_use;
741 } catch (const Gecode::Search::InvalidWorkerRequest&) {
742 caught = !in_use;
743 }
744 return caught && (live == (clone ? 1 : 0));
745 }
746 public:
747 PBSConstructionFailure(void) : Base("Search::PBS::ConstructionFailure", TestTags::check()) {}
748 bool run(void) override {
749 for (unsigned int threads : {1U,4U})
750 for (bool clone : {false,true})
751 for (int failing : {-1,0,1}) {
752 int live = 0;
753 std::unique_ptr<PortfolioSeed> root(new PortfolioSeed(live));
754 PortfolioSeed* seed = root.get();
755 if (!clone)
756 root.release();
758 o.assets = 2;
759 o.threads = threads;
760 o.clone = clone;
761 bool caught = false;
762 try {
763 if (failing == -1) {
765 } else {
766 Gecode::SEBs sebs(2);
768 sebs[1-failing] = Gecode::dfs<PortfolioSeed>();
769 Gecode::PBS<PortfolioSeed> engine(seed,sebs,o);
770 }
771 } catch (const Gecode::Search::UninitializedCutoff&) {
772 caught = true;
773 }
774 if (!caught || (live != (clone ? 1 : 0)))
775 return false;
776 }
777 for (unsigned int threads : {1U,4U})
778 for (bool clone : {false,true})
779 for (bool restart : {false,true})
780 for (bool in_use : {false,true})
781 if (!worker_control_failure(threads,clone,restart,in_use))
782 return false;
783 return true;
784 }
785 };
786
788
791 class Pause : public Gecode::Search::Stop {
793 unsigned int node;
794 std::atomic<bool> paused;
795 public:
796 std::promise<void> reached;
797 Pause(const Gecode::Search::WorkerControl& c, unsigned int n)
798 : control(c), node(n), paused(false) {}
799 bool stop(const Gecode::Search::Statistics& s,
800 const Gecode::Search::Options&) override {
801 if ((s.node >= node) && !paused.exchange(true)) {
802 control.request(0U);
803 reached.set_value();
804 }
805 return false;
806 }
807 };
808 template<template<class> class E>
809 bool check(unsigned int node, unsigned int threads) {
810 Gecode::Search::WorkerControl control(node == 0U ? 0U : threads);
811 Pause pause(control,node);
813 o.threads = threads;
814 o.worker_control = control;
815 o.stop = &pause;
817 E<HasSolutions> engine(&root,o);
818 auto result = std::async(std::launch::async,[&] { return engine.next(); });
819 auto reached = pause.reached.get_future();
820 reached.wait();
821 bool ok = result.wait_for(std::chrono::milliseconds(20)) ==
822 std::future_status::timeout;
823 control.request(1U);
824 int solutions = 0;
825 if (HasSolutions* solution = result.get()) {
826 ++solutions;
827 delete solution;
828 }
829 // Alternate expansion and shrinking at solution boundaries. This
830 // exercises each request while preserving complete enumeration.
831 while (true) {
832 control.request((solutions % 2) ? threads : 1U);
833 HasSolutions* solution = engine.next();
834 if (!solution)
835 break;
836 ++solutions;
837 delete solution;
838 }
839 return ok && !engine.stopped() && (solutions == root.solutions());
840 }
841#ifdef GECODE_HAS_EXPERIMENTAL
842 template<template<class> class E>
843 bool heuristic(unsigned int node, unsigned int threads) {
844 Gecode::Search::WorkerControl control(node == 0U ? 0U : 1U);
845 Pause pause(control,node);
846 TreeSpace root(TreeSpace::random(_rand,4),false);
848 TreeSpace::guidance(false,true,false,false);
850 o.threads = threads;
851 o.worker_control = control;
852 o.stop = &pause;
853 o.guidance = &g;
854 E<TreeSpace> engine(&root,o);
855 int last = std::numeric_limits<int>::max();
856 auto consume = [&] {
857 while (TreeSpace* s = engine.next()) {
858 last = s->node().cost;
859 delete s;
860 }
861 };
862 auto result = std::async(std::launch::async,consume);
863 pause.reached.get_future().wait();
864 bool ok = result.wait_for(std::chrono::milliseconds(20)) ==
865 std::future_status::timeout;
866 control.request(threads);
867 result.get();
868 return ok && !engine.stopped() && (last == (*root.graph)[0].best);
869 }
870#endif
871
872 public:
874 : Base("Search::WorkerControl::SequentialPause", TestTags::check()) {}
875 bool run(void) override {
876#ifdef GECODE_HAS_THREADS
877#ifdef GECODE_HAS_EXPERIMENTAL
878 for (unsigned int node : {0U,1U})
879 for (unsigned int threads : {1U,4U})
880 if (!heuristic<Gecode::AStar>(node,threads) ||
881 !heuristic<Gecode::CABS>(node,threads))
882 return false;
883#endif
884 for (unsigned int threads : {1U,4U})
885 if (!check<Gecode::DFS>(0U,threads) ||
886 !check<Gecode::DFS>(1U,threads) ||
887 !check<Gecode::BAB>(0U,threads) ||
888 !check<Gecode::BAB>(1U,threads))
889 return false;
890 return true;
891#else
892 return true;
893#endif
894 }
895 };
896
898
901 private:
903 template<class Engine>
904 bool drain(Engine& engine,
905 std::vector<Gecode::Search::WorkerControl> controls,
906 unsigned int capacity, int& solutions, bool& best) {
907 std::atomic<bool> done(false);
908 std::vector<std::thread> resizers;
909 for (Gecode::Search::WorkerControl& control : controls)
910 resizers.emplace_back([&done,&control,capacity,seed=_rand.next()] {
911 Gecode::Support::RandomGenerator rand(seed);
912 while (!done.load(std::memory_order_acquire)) {
913 control.request(rand(capacity+1U));
914 std::this_thread::yield();
915 }
916 });
917 HasSolutions* last = nullptr;
918 solutions = 0;
919 while (HasSolutions* s = engine.next()) {
920 ++solutions;
921 delete last;
922 last = s;
923 }
924 done.store(true,std::memory_order_release);
925 for (std::thread& resizer : resizers)
926 resizer.join();
927 best = (last != nullptr) && last->best();
928 delete last;
929 return !engine.stopped();
930 }
931 public:
933 : Base("Search::WorkerControl::ConcurrentResize", TestTags::check()) {}
934 bool run(void) override {
935#ifdef GECODE_HAS_THREADS
937 const unsigned int threads = 4U;
938 int n;
939 bool best;
940 {
942 WorkerControl control(threads);
944 o.threads = threads;
945 o.worker_control = control;
947 if (!drain(dfs,{control},threads,n,best) || (n != root.solutions()))
948 return false;
949 }
950 {
952 WorkerControl control(threads);
954 o.threads = threads;
955 o.worker_control = control;
957 if (!drain(bab,{control},threads,n,best) || !best)
958 return false;
959 }
960 {
961 // Restarts rebuild the leaf engine under the same control.
963 WorkerControl control(threads);
965 o.threads = threads;
966 o.worker_control = control;
969 if (!drain(rbs,{control},threads,n,best) || !best ||
970 (rbs.statistics().restart == 0))
971 return false;
972 }
973 {
975 WorkerControl controls[2] = {WorkerControl(threads),
976 WorkerControl(threads)};
977 Gecode::SEBs sebs(2);
978 for (int i=0; i<2; i++) {
980 leaf.threads = threads;
981 leaf.worker_control = controls[i];
982 sebs[i] = Gecode::bab<HasSolutions>(leaf);
983 }
985 o.threads = 2.0;
987 if (!drain(pbs,{controls[0],controls[1]},threads,n,best) || !best)
988 return false;
989 }
990#endif
991 return true;
992 }
993 };
994
996
998 class WorkerControlAPI : public Base {
999 private:
1000 template<class Exception, class Function>
1001 static bool throws(Function function) {
1002 try {
1003 function();
1004 } catch (const Exception&) {
1005 return true;
1006 } catch (...) {
1007 }
1008 return false;
1009 }
1010 public:
1011 WorkerControlAPI(void) : Base("Search::WorkerControl::API", TestTags::check()) {}
1012 bool run(void) override {
1014 WorkerControl empty;
1015 bool ok = !empty.engaged() && (empty.requested() == 0U) &&
1016 (empty.capacity() == 0U) &&
1017 throws<Gecode::Search::UninitializedWorkerControl>(
1018 [&] { empty.request(1U); });
1019
1020 const unsigned int capacity = worker_capacity(2U);
1021 WorkerControl control(0U);
1022 WorkerControl copy(control);
1024 ok = ok && copy.engaged() && (copy.requested() == 0U);
1025
1027 o.threads = 2.0;
1028 o.worker_control = control;
1029 SolveImmediate* root =
1031#ifndef GECODE_HAS_THREADS
1032 ok = ok && throws<Gecode::Search::InvalidWorkerRequest>(
1033 [&] { Gecode::DFS<SolveImmediate> engine(root,o); });
1034 control.request(1U);
1035 ok = ok && throws<Gecode::Search::InvalidWorkerRequest>(
1036 [&] { control.request(0U); });
1037#endif
1038 {
1039 Gecode::DFS<SolveImmediate> engine(root,o);
1040 delete root;
1041 root = nullptr;
1042 ok = ok && (control.capacity() == capacity);
1043 ok = ok && throws<Gecode::Search::WorkerControlInUse>([&] {
1045 });
1046 control.request(1U);
1047 ok = ok && (copy.requested() == 1U) &&
1048 throws<Gecode::Search::InvalidWorkerRequest>(
1049 [&] { control.request(capacity+1U); });
1050 delete engine.next();
1051 }
1053 ok = ok && throws<Gecode::Search::WorkerControlInUse>(
1054 [&] { Gecode::DFS<SolveImmediate> engine(root,o); });
1055 delete root;
1058#ifdef GECODE_HAS_THREADS
1059 copy.request(0U);
1060 ok = ok && (control.requested() == 0U);
1061#endif
1062 ok = ok && (control.capacity() == capacity) &&
1063 throws<Gecode::Search::InvalidWorkerRequest>([&] {
1065 });
1067 {
1068 Gecode::DFS<SolveImmediate> engine(root,o);
1069 delete root;
1070 copy.request(1U);
1071 delete engine.next();
1072 }
1073 return ok;
1074 }
1075 };
1076
1078
1081 public:
1083 : Base("Search::WorkerControl::PBS::Pause", TestTags::check()) {}
1084 bool run(void) override {
1085 bool ok = true;
1086 // A sequential portfolio must reject assets that could block its round.
1087 for (unsigned int requested : {0U,1U}) {
1090 Gecode::SEBs sebs(2);
1091 sebs[0] = Gecode::dfs<SolveImmediate>(leaf);
1092 sebs[1] = Gecode::dfs<SolveImmediate>();
1095 o.threads = 1.0;
1096 bool rejected = false;
1097 try {
1098 Gecode::PBS<SolveImmediate> pbs(&root,sebs,o);
1099 } catch (const Gecode::Search::WorkerControlInUse&) {
1100 rejected = true;
1101 delete sebs[0];
1102 delete sebs[1];
1103 }
1104 ok = ok && rejected;
1105 }
1106#ifdef GECODE_HAS_THREADS
1107 for (unsigned int threads : {1U,2U})
1108 for (bool restart : {false,true}) {
1110 Gecode::Search::Options paused_options;
1111 paused_options.threads = threads;
1112 paused_options.worker_control = paused;
1113
1114 Gecode::Search::Options active_options;
1115 active_options.threads = 2.0;
1116
1117 Gecode::SEBs sebs(2);
1118 if (restart) {
1119 paused_options.cutoff = Gecode::Search::Cutoff::constant(1000);
1120 sebs[0] = Gecode::rbs<SolveImmediate,Gecode::DFS>(paused_options);
1121 } else {
1122 sebs[0] = Gecode::dfs<SolveImmediate>(paused_options);
1123 }
1124 sebs[1] = Gecode::dfs<SolveImmediate>(active_options);
1125
1126 Gecode::Search::Options portfolio_options;
1127 portfolio_options.threads = 2.0;
1128 SolveImmediate* root =
1131 pbs(root,sebs,portfolio_options);
1132 delete root;
1133
1134 SolveImmediate* solution = pbs.next();
1135 ok = ok && (solution != nullptr) && (paused.requested() == 0U);
1136 delete solution;
1137 }
1138#endif
1139 return ok;
1140 }
1141 };
1142
1144
1146 template<class Model>
1147 class DFS : public Test {
1148 private:
1150 unsigned int c_d;
1152 unsigned int a_d;
1154 unsigned int t;
1155 public:
1159 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
1160 : Test(tags,"DFS::"+Model::name()+"::"+
1161 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
1162 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
1163 htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
1164
1165 virtual bool run(void) {
1166 Model* m = new Model(htb1,htb2,htb3);
1169 o.c_d = c_d;
1170 o.a_d = a_d;
1171 o.threads = t;
1172 o.stop = &f;
1174 int n = m->solutions();
1175 delete m;
1176 while (true) {
1177 Model* s = dfs.next();
1178 if (s != nullptr) {
1179 n--; delete s;
1180 }
1181 if ((s == nullptr) && !dfs.stopped())
1182 break;
1183 f.limit(f.limit()+2);
1184 }
1185 return n == 0;
1186 }
1187 };
1188
1190 template<class Model>
1191 class LDS : public Test {
1192 private:
1194 unsigned int t;
1195 public:
1198 unsigned int t0)
1199 : Test("LDS::"+Model::name()+"::"+
1200 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
1201 htb1,htb2,htb3), t(t0) {}
1202
1203 virtual bool run(void) {
1204 Model* m = new Model(htb1,htb2,htb3);
1207 o.threads = t;
1208 o.d_l = 50;
1209 o.stop = &f;
1211 int n = m->solutions();
1212 delete m;
1213 while (true) {
1214 Model* s = lds.next();
1215 if (s != nullptr) {
1216 n--; delete s;
1217 }
1218 if ((s == nullptr) && !lds.stopped())
1219 break;
1220 f.limit(f.limit()+2);
1221 }
1222 return n == 0;
1223 }
1224 };
1225
1227 template<class Model>
1228 class BAB : public Test {
1229 private:
1231 unsigned int c_d;
1233 unsigned int a_d;
1235 unsigned int t;
1236 public:
1240 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
1241 : Test(tags,"BAB::"+Model::name()+"::"+str(htc)+"::"+
1242 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
1243 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
1244 htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
1245
1246 virtual bool run(void) {
1247 Model* m = new Model(htb1,htb2,htb3,htc);
1250 o.c_d = c_d;
1251 o.a_d = a_d;
1252 o.threads = t;
1253 o.stop = &f;
1255 delete m;
1256 Model* b = nullptr;
1257 while (true) {
1258 Model* s = bab.next();
1259 if (s != nullptr) {
1260 delete b; b=s;
1261 }
1262 if ((s == nullptr) && !bab.stopped())
1263 break;
1264 f.limit(f.limit()+2);
1265 }
1266 bool ok = (b == nullptr) || b->best();
1267 delete b;
1268 return ok;
1269 }
1270 };
1271
1273 template<class Model, template<class> class Engine>
1274 class RBS : public Test {
1275 private:
1277 unsigned int t;
1278 public:
1280 RBS(const std::string& e, unsigned int t0)
1281 : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
1283
1284 virtual bool run(void) {
1285 Model* m = new Model(htb1,htb2,htb3);
1288 o.threads = t;
1289 o.stop = &f;
1290 o.d_l = 100;
1293 int n = m->solutions();
1294 delete m;
1295 while (true) {
1296 Model* s = rbs.next();
1297 if (s != nullptr) {
1298 n--; delete s;
1299 }
1300 if ((s == nullptr) && !rbs.stopped())
1301 break;
1302 f.limit(f.limit()+2);
1303 }
1304 return n == 0;
1305 }
1306 };
1307
1310 public:
1313 RestrictedFirstSlave(void) : x(*this,4,0,3) {
1314 Gecode::distinct(*this,x);
1316 }
1318 : Gecode::IntMinimizeSpace(s) {
1319 x.update(*this,s.x);
1320 }
1321 Gecode::Space* copy(void) override {
1322 return new RestrictedFirstSlave(*this);
1323 }
1324 Gecode::IntVar cost(void) const override {
1325 return x[0];
1326 }
1327 bool slave(const Gecode::MetaInfo& mi) override {
1328 if ((mi.type() == Gecode::MetaInfo::RESTART) &&
1330 Gecode::dom(*this,x[2],0,1);
1331 Gecode::dom(*this,x[3],0,1);
1332 return false;
1333 }
1334 return true;
1335 }
1336 };
1337
1340 public:
1341 RBSIncompleteNoGoods(void) : Base("Search::RBS::IncompleteNoGoods") {}
1342 bool run(void) override {
1345 o.nogoods_limit = 128U;
1348 delete m;
1349 // The restricted search finds x0 = 2 and rules out x0 in {0,1}
1350 int best = -1;
1351 while (RestrictedFirstSlave* s = rbs.next()) {
1352 best = s->x[0].val();
1353 delete s;
1354 }
1355 return !rbs.stopped() && (best == 0);
1356 }
1357 };
1358
1360
1363 public:
1366 NoSolution(void) : x(*this,4,0,2) {
1367 for (int i=0; i<x.size(); i++)
1368 for (int j=i+1; j<x.size(); j++)
1369 Gecode::rel(*this,x[i],Gecode::IRT_NQ,x[j]);
1371 }
1373 x.update(*this,s.x);
1374 }
1375 Gecode::Space* copy(void) override {
1376 return new NoSolution(*this);
1377 }
1378 Gecode::IntVar cost(void) const override {
1379 return x[0];
1380 }
1381 bool master(const Gecode::MetaInfo& mi) override {
1382 // Keep the branchers for the assets of a portfolio
1384 return true;
1386 }
1387 };
1388
1390 class FailingMaster : public NoSolution {
1391 public:
1392 FailingMaster(void) = default;
1394 Gecode::Space* copy(void) override {
1395 return new FailingMaster(*this);
1396 }
1397 bool master(const Gecode::MetaInfo& mi) override {
1398 if ((mi.type() == Gecode::MetaInfo::RESTART) &&
1400 fail();
1401 return true;
1402 }
1403 };
1404
1406 class RBSFailedMaster : public Base {
1407 public:
1408 RBSFailedMaster(void) : Base("Search::RBS::FailedMaster") {}
1409 bool run(void) override {
1410 for (unsigned int t : {1U,2U}) {
1413 o.threads = t;
1416 delete m;
1417 if (FailingMaster* s = rbs.next()) {
1418 delete s;
1419 return false;
1420 }
1421 Gecode::Search::Statistics s = rbs.statistics();
1422 // The failures of the last slave search are counted once
1423 if (rbs.stopped() || (s.restart != 1U) || (s.fail < 2U) ||
1424 ((t == 1U) && (s.fail != 2U)))
1425 return false;
1426 if ((rbs.next() != nullptr) || rbs.stopped() ||
1427 (rbs.statistics().fail != s.fail) ||
1428 (rbs.statistics().node != s.node))
1429 return false;
1430 }
1431 return true;
1432 }
1433 };
1434
1436
1438 class FailingSlave : public NoSolution {
1439 public:
1440 FailingSlave(void) = default;
1442 Gecode::Space* copy(void) override {
1443 return new FailingSlave(*this);
1444 }
1445 bool slave(const Gecode::MetaInfo& mi) override {
1446 if ((mi.type() == Gecode::MetaInfo::RESTART) && (mi.restart() > 0)) {
1447 fail();
1448 return false;
1449 }
1450 return true;
1451 }
1452 };
1453
1456 public:
1458 unsigned long int checks = 0;
1460 const Gecode::Search::Options&) override {
1461 return (s.fail >= 5) || (++checks > 1000);
1462 }
1463 };
1464
1466 class RBSRootFailure : public Base {
1467 template<template<class> class Engine>
1468 static bool test(unsigned int threads) {
1469 FailingSlave* m = new FailingSlave;
1470 FiveFailures f;
1472 o.threads = threads;
1473 o.stop = &f;
1476 delete m;
1477 if (FailingSlave* s = rbs.next()) {
1478 delete s;
1479 return false;
1480 }
1481 return rbs.stopped() && (f.checks <= 1000) &&
1482 (rbs.statistics().fail >= 5);
1483 }
1484 public:
1485 RBSRootFailure(void) : Base("Search::RBS::RootFailure") {}
1486 bool run(void) override {
1487 return test<Gecode::DFS>(1U) && test<Gecode::DFS>(2U) &&
1488 test<Gecode::BAB>(1U) && test<Gecode::BAB>(2U) &&
1489 test<Gecode::LDS>(1U);
1490 }
1491 };
1492
1494
1497 public:
1498 FailingFirstSlave(void) = default;
1500 Gecode::Space* copy(void) override {
1501 return new FailingFirstSlave(*this);
1502 }
1503 bool slave(const Gecode::MetaInfo& mi) override {
1504 if ((mi.type() == Gecode::MetaInfo::RESTART) &&
1506 fail();
1507 return false;
1508 }
1509 return true;
1510 }
1511 };
1512
1514 class RBSFailedFirstSlave : public Base {
1515 template<template<class> class Engine>
1516 static bool test(unsigned int threads) {
1519 o.threads = threads;
1522 delete m;
1523 FailingFirstSlave* s = rbs.next();
1524 if (s == nullptr)
1525 return false;
1526 delete s;
1527 return rbs.statistics().restart >= 1U;
1528 }
1529 public:
1530 RBSFailedFirstSlave(void) : Base("Search::RBS::FailedFirstSlave") {}
1531 bool run(void) override {
1532 return test<Gecode::DFS>(1U) && test<Gecode::DFS>(2U) &&
1533 test<Gecode::BAB>(1U) && test<Gecode::BAB>(2U) &&
1534 test<Gecode::LDS>(1U);
1535 }
1536 };
1537
1539
1542 public:
1544 unsigned long long int limit;
1546 std::atomic<unsigned long int> checks{0};
1547 FailureLimit(unsigned long long int l) : limit(l) {}
1549 const Gecode::Search::Options&) override {
1550 return (s.fail > limit) || (++checks > 1000);
1551 }
1552 };
1553
1555 class ExhaustedAtLimit : public Base {
1556 template<template<class> class Engine>
1557 static bool test(void) {
1558 NoSolution root;
1559 unsigned long long int f;
1560 {
1561 Engine<NoSolution> e(&root);
1562 if (NoSolution* s = e.next()) {
1563 delete s;
1564 return false;
1565 }
1566 f = e.statistics().fail;
1567 }
1568 if (f < 2)
1569 return false;
1570 // The search is exhausted at the failure that exceeds the limit
1571 {
1572 FailureLimit l(f-1);
1574 o.stop = &l;
1575 Engine<NoSolution> e(&root,o);
1576 if ((e.next() != nullptr) || e.stopped())
1577 return false;
1578 }
1579 // Restarts at that limit post no no-goods and would repeat forever
1580 {
1581 FailureLimit l(1000);
1583 o.stop = &l;
1584 o.nogoods_limit = 128U;
1587 if ((rbs.next() != nullptr) || rbs.stopped())
1588 return false;
1589 }
1590 return true;
1591 }
1592 public:
1593 ExhaustedAtLimit(void) : Base("Search::ExhaustedAtLimit") {}
1594 bool run(void) override {
1595 return test<Gecode::DFS>() && test<Gecode::BAB>();
1596 }
1597 };
1598
1600
1602 class RelaxSpace : public Gecode::Space {
1603 public:
1604 RelaxSpace(void) = default;
1606 Gecode::Space* copy(void) override {
1607 return new RelaxSpace(*this);
1608 }
1609 };
1610
1612 class RelaxFailed : public Base {
1613 public:
1614 RelaxFailed(void) : Base("Search::Relax::Failed") {}
1615 bool run(void) override {
1616 RelaxSpace s;
1617 // The kept value lies in a hole of the domain
1618 Gecode::IntVarArgs x(s,2,Gecode::IntSet({0,2}));
1619 Gecode::IntVarArgs sx(s,2,1,1);
1620 // Probability zero keeps one of the two values
1621 Gecode::relax(s,x,sx,Gecode::Rnd(1U),0.0);
1622 return s.failed();
1623 }
1624 };
1625
1627
1629 template<class Model, template<class> class Engine>
1630 class PBS : public Test {
1631 private:
1633 bool best;
1635 unsigned int a;
1637 unsigned int t;
1638 public:
1640 PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
1641 : Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
1642 HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
1643
1644 virtual bool run(void) {
1645 Model* m = new Model(htb1,htb2,htb3);
1648 o.assets = a;
1649 o.threads = t;
1650 o.d_l = 100;
1651 o.stop = &f;
1653 if (best) {
1654 delete m;
1655 Model* b = nullptr;
1656 while (true) {
1657 Model* s = pbs.next();
1658 if (s != nullptr) {
1659 delete b; b=s;
1660 }
1661 if ((s == nullptr) && !pbs.stopped())
1662 break;
1663 f.limit(f.limit()+2);
1664 }
1665 bool ok = (b == nullptr) || b->best();
1666 delete b;
1667 return ok;
1668 } else {
1669 int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
1670 delete m;
1671 while (true) {
1672 Model* s = pbs.next();
1673 if (s != nullptr) {
1674 n--; delete s;
1675 }
1676 if ((s == nullptr) && !pbs.stopped())
1677 break;
1678 f.limit(f.limit()+2);
1679 }
1680 return n >= 0;
1681 }
1682 }
1683 };
1684
1686 template<class Model>
1687 class SEBPBS : public Test {
1688 private:
1690 bool best;
1692 unsigned int mt;
1694 unsigned int st;
1695 public:
1697 SEBPBS(const std::string& e, bool b, unsigned int mt0, unsigned int st0)
1698 : Test("PBS::SEB::"+e+"::"+Model::name()+"::"+str(mt0)+"::"+str(st0),
1699 HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
1700
1701 virtual bool run(void) {
1702 using namespace Gecode;
1703 Model* m = new Model(htb1,htb2,htb3);
1705
1707 mo.threads = mt;
1708 mo.d_l = 100;
1709 mo.stop = &f;
1710
1712 so.threads = st;
1713 so.d_l = 100;
1715 if (best) {
1716 SEBs sebs(3);
1717 sebs[0] = bab<Model>(so);
1718 sebs[1] = bab<Model>(so);
1719 sebs[2] = rbs<Model,Gecode::BAB>(so);
1721 delete m;
1722
1723 Model* b = nullptr;
1724 while (true) {
1725 Model* s = pbs.next();
1726 if (s != nullptr) {
1727 delete b; b=s;
1728 }
1729 if ((s == nullptr) && !pbs.stopped())
1730 break;
1731 f.limit(f.limit()+2);
1732 }
1733 bool ok = (b == nullptr) || b->best();
1734 delete b;
1735 return ok;
1736 } else {
1737 SEBs sebs(3);
1738 sebs[0] = dfs<Model>(so);
1739 sebs[1] = lds<Model>(so);
1740 sebs[2] = rbs<Model,Gecode::DFS>(so);
1742
1743 int n = 3 * m->solutions();
1744 delete m;
1745
1746 while (true) {
1747 Model* s = pbs.next();
1748 if (s != nullptr) {
1749 n--; delete s;
1750 }
1751 if ((s == nullptr) && !pbs.stopped())
1752 break;
1753 f.limit(f.limit()+2);
1754 }
1755 return n >= 0;
1756 }
1757 }
1758 };
1759
1761 class PBSBuilderStop : public Base {
1763 typedef Gecode::SEB (*Builder)(const Gecode::Search::Options&);
1764 template<template<class> class Engine>
1765 static bool test(unsigned int threads, Builder builder) {
1766 NoSolution root;
1767 FailureLimit l(1);
1769 o.threads = threads;
1770 o.stop = &l;
1771 Gecode::SEBs sebs(2);
1772 sebs[0] = builder(Gecode::Search::Options::def);
1773 sebs[1] = builder(Gecode::Search::Options::def);
1774 Gecode::PBS<NoSolution,Engine> pbs(&root,sebs,o);
1775 return (pbs.next() == nullptr) && pbs.stopped() && (l.checks <= 1000);
1776 }
1777 public:
1778 PBSBuilderStop(void) : Base("Search::PBS::SEB::Stop") {}
1779 bool run(void) override {
1780 for (unsigned int t : {1U,2U})
1781 if (!test<Gecode::DFS>(t,&Gecode::dfs<NoSolution>) ||
1782 !test<Gecode::BAB>(t,&Gecode::bab<NoSolution>))
1783 return false;
1784 return true;
1785 }
1786 };
1787
1789
1791 class PBSRestartCutoff : public Base {
1792 template<template<class> class Engine>
1793 static bool test(unsigned int threads) {
1794 NoSolution root;
1796 o.assets = 2;
1797 o.threads = threads;
1800 return (pbs.next() == nullptr) && !pbs.stopped();
1801 }
1802 public:
1803 PBSRestartCutoff(void) : Base("Search::PBS::RBS::Cutoff") {}
1804 bool run(void) override {
1805 for (unsigned int t : {1U,2U,4U})
1806 if (!test<Gecode::RBS>(t) || !test<RestartPortfolio>(t))
1807 return false;
1808 return true;
1809 }
1810 };
1811
1813
1822 public:
1824 std::atomic<unsigned int>& deleted;
1825 CountingCutoff(std::atomic<unsigned int>& d)
1826 : Gecode::Search::CutoffConstant(1000), deleted(d) {}
1827 ~CountingCutoff(void) override {
1828 deleted++;
1829 }
1830 };
1831
1833 class FailingAsset : public NoSolution {
1834 public:
1835 FailingAsset(void) = default;
1837 Gecode::Space* copy(void) override {
1838 return new FailingAsset(*this);
1839 }
1840 bool slave(const Gecode::MetaInfo& mi) override {
1841 if ((mi.type() == Gecode::MetaInfo::PORTFOLIO) && (mi.asset() == 0U))
1842 fail();
1843 return true;
1844 }
1845 };
1846
1849 template<class Root, template<class> class Engine>
1850 static bool test(Root& root, unsigned int threads) {
1851 std::atomic<unsigned int> deleted{0U};
1852 {
1854 o.assets = 2;
1855 o.threads = threads;
1856 o.cutoff = new CountingCutoff(deleted);
1858 if (Root* s = pbs.next()) {
1859 delete s;
1860 return false;
1861 }
1862 if (pbs.stopped())
1863 return false;
1864 }
1865 return deleted == 1U;
1866 }
1867 public:
1869 : Base("Search::PBS::RBS::CutoffDeleted") {}
1870 bool run(void) override {
1871 // A failed root, also for a portfolio of portfolios
1872 NoSolution failed;
1873 Gecode::rel(failed,failed.x[0],Gecode::IRT_LE,0);
1874 // An asset of a portfolio of portfolios fails at its root
1875 FailingAsset failing;
1876 for (unsigned int t : {1U,2U,4U})
1877 if (!test<NoSolution,Gecode::RBS>(failed,t) ||
1878 !test<NoSolution,RestartPortfolio>(failed,t) ||
1879 !test<FailingAsset,Gecode::RBS>(failing,t) ||
1880 !test<FailingAsset,RestartPortfolio>(failing,t))
1881 return false;
1882 return true;
1883 }
1884 };
1885
1887
1890 private:
1892 static const HowToBranch htbs[3];
1894 int i;
1895 public:
1897 BranchTypes(void) : i(0) {}
1899 bool operator()(void) const {
1900 return i<3;
1901 }
1902
1903 void operator++(void) {
1904 i++;
1905 }
1906
1907 HowToBranch htb(void) const {
1908 return htbs[i];
1909 }
1910 };
1911
1912 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
1913
1916 private:
1918 static const HowToConstrain htcs[4];
1920 int i;
1921 public:
1923 ConstrainTypes(void) : i(0) {}
1925 bool operator()(void) const {
1926 return i<4;
1927 }
1928
1929 void operator++(void) {
1930 i++;
1931 }
1932
1933 HowToConstrain htc(void) const {
1934 return htcs[i];
1935 }
1936 };
1937
1938 const HowToConstrain ConstrainTypes::htcs[4] =
1939 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
1940
1941
1943 class Create {
1944 public:
1946 Create(void) {
1947 // Depth-first search
1948 for (unsigned int t = 1; t<=4; t++)
1949 for (unsigned int c_d = 1; c_d<10; c_d++)
1950 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
1951 for (BranchTypes htb1; htb1(); ++htb1)
1952 for (BranchTypes htb2; htb2(); ++htb2)
1953 for (BranchTypes htb3; htb3(); ++htb3)
1954 (void) new DFS<HasSolutions>
1955 ((htb1.htb() == HTB_BINARY) &&
1956 (htb2.htb() == HTB_NARY) &&
1957 (htb3.htb() == HTB_BINARY) &&
1958 (c_d == 1) && (a_d == 1) && (t == 1)
1959 ? TestTags::check()
1961 htb1.htb(),htb2.htb(),htb3.htb(),c_d,a_d,t);
1964 c_d, a_d, t);
1967 c_d, a_d, t);
1970 c_d, a_d, t);
1971 }
1972
1973 // Limited discrepancy search
1974 for (unsigned int t = 1; t<=4; t++) {
1975 for (BranchTypes htb1; htb1(); ++htb1)
1976 for (BranchTypes htb2; htb2(); ++htb2)
1977 for (BranchTypes htb3; htb3(); ++htb3)
1978 (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
1979 ,t);
1982 }
1983
1984 // Best solution search
1985 for (unsigned int t = 1; t<=4; t++)
1986 for (unsigned int c_d = 1; c_d<10; c_d++)
1987 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
1988 for (ConstrainTypes htc; htc(); ++htc)
1989 for (BranchTypes htb1; htb1(); ++htb1)
1990 for (BranchTypes htb2; htb2(); ++htb2)
1991 for (BranchTypes htb3; htb3(); ++htb3) {
1992 (void) new BAB<HasSolutions>
1993 ((htc.htc() == HTC_BAL_GR) &&
1994 (htb1.htb() == HTB_BINARY) &&
1995 (htb2.htb() == HTB_BINARY) &&
1996 (htb3.htb() == HTB_BINARY) &&
1997 (c_d == 1) && (a_d == 1) && (t == 1)
2000 htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
2001 c_d,a_d,t);
2002 }
2003 (void) new BAB<FailImmediate>
2005 c_d,a_d,t);
2006 (void) new BAB<SolveImmediate>
2008 c_d,a_d,t);
2009 (void) new BAB<HasSolutions>
2011 c_d,a_d,t);
2012 }
2013 // Restart-based search
2014 for (unsigned int t=1; t<=4; t++) {
2015 (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
2016 (void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
2017 (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
2018 (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
2019 (void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
2020 (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
2021 (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
2022 (void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
2023 (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
2024 }
2025 // Portfolio-based search
2026 for (unsigned int a=1; a<=4; a++)
2027 for (unsigned int t=1; t<=2*a; t++) {
2028 (void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
2029 (void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
2030 (void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
2031 (void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
2032 (void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
2033 (void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
2034 (void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
2035 (void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
2036 (void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
2037 }
2038 // Portfolio-based search using SEBs
2039 for (unsigned int mt=1; mt<=3; mt += 2)
2040 for (unsigned int st=1; st<=8; st++) {
2041 (void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
2042 (void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
2043 (void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
2044 (void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
2045 (void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
2046 (void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
2047 }
2048 }
2049 };
2050
2052 }
2053
2054}
2055
2056// STATISTICS: test-search
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Archive representation
Definition archive.hpp:42
Depth-first branch-and-bound search engine.
Definition search.hh:1373
Passing Boolean variables.
Definition int.hh:739
friend class Space
Definition core.hpp:1462
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3822
friend class Choice
Definition core.hpp:1463
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:958
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3999
Depth-first search engine.
Definition search.hh:1211
Exception: Base-class for exceptions
Definition exception.hpp:42
Home class for posting propagators
Definition core.hpp:863
Class for minimizing integer cost.
IntMinimizeSpace(void)
Default constructor.
Definition optimize.hpp:37
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Limited discrepancy search engine.
Definition search.hh:1423
Information passed by meta search engines.
Definition core.hpp:1635
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1642
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1640
unsigned int asset(void) const
Return number of asset in portfolio.
Definition core.hpp:3265
unsigned long int restart(void) const
Return number of restarts.
Definition core.hpp:3236
const Space * last(void) const
Return last solution found (possibly nullptr).
Definition core.hpp:3255
RestartReason reason(void) const
Return reason for restarting.
Definition core.hpp:3241
@ RR_INIT
Restarting after initialisation.
Definition core.hpp:1649
@ RR_LIM
Restarting after reaching restart limit.
Definition core.hpp:1655
Type type(void) const
Return type of information.
Definition core.hpp:3232
Meta engine using a portfolio of search engines.
Definition search.hh:1563
Meta-engine performing restart-based search.
Definition search.hh:1471
Random number generator.
Definition rnd.hpp:42
Passing search engine builder arguments.
Definition search.hh:1177
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition base.hpp:56
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
Cutoff generator for constant sequence.
Definition search.hh:534
CutoffConstant(unsigned long long int c)
Constructor.
Definition cutoff.hpp:47
static Cutoff * constant(unsigned long long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition cutoff.cpp:148
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
Stop-object based on number of failures
Definition search.hh:978
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
Evaluate rank
Node rank (optional, lower first).
Definition search.hh:1270
Exception: Invalid requested number of search workers
Definition exception.hpp:66
Search engine options
Definition search.hh:848
static const Options def
Default options.
Definition search.hh:889
unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:863
WorkerControl worker_control
Definition search.hh:861
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
unsigned int d_l
Discrepancy limit (for LDS, reaching it does not stop the engine).
Definition search.hh:867
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:877
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:865
Stop * stop
Stop object for stopping search.
Definition search.hh:875
unsigned long int max_width
Maximal beam width for CABS (zero for no limit).
Definition search.hh:884
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:869
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition search.hh:873
double threads
Number of threads to use.
Definition search.hh:853
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
Base-class for Stop-object.
Definition search.hh:919
Exception: Uninitialized cutoff for restart-based search
Definition exception.hpp:42
static void prepare_reuse(WorkerControl &control)
Prepare control for another engine with the same capacity.
static void attach(WorkerControl &control, unsigned int capacity)
Attach control to a leaf engine with fixed capacity.
Exception: Worker control is already bound or used in an unsupported engine
Definition exception.hpp:78
External control for the requested number of search workers.
Definition search.hh:773
bool engaged(void) const noexcept
Whether this handle is engaged.
unsigned int requested(void) const noexcept
Return the requested number of workers (zero also denotes an empty handle).
Computation spaces.
Definition core.hpp:1787
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Graph specification
Definition ind-set.cpp:47
Gecode::Support::RandomGenerator _rand
Random number generator.
Definition test.hh:238
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
const std::string & name(void) const
Return name of test.
Definition test.hpp:91
TestTags tags(void) const
Return tags for test.
Definition test.hpp:95
BAB(TestTags tags, HowToConstrain htc, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:1238
virtual bool run(void)
Run test.
Definition search.cpp:1246
Iterator for branching types.
Definition search.cpp:1889
HowToBranch htb(void) const
Return current branching type.
Definition search.cpp:1907
BranchTypes(void)
Initialize iterator.
Definition search.cpp:1897
void operator++(void)
Increment to next branching type.
Definition search.cpp:1903
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:1899
Iterator for constrain types.
Definition search.cpp:1915
HowToConstrain htc(void) const
Return current constrain type.
Definition search.cpp:1933
void operator++(void)
Increment to next constrain type.
Definition search.cpp:1929
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:1925
ConstrainTypes(void)
Initialize iterator.
Definition search.cpp:1923
Constant cutoff counting its deletions.
Definition search.cpp:1821
~CountingCutoff(void) override
Definition search.cpp:1827
std::atomic< unsigned int > & deleted
Number of deletions, owned by the test.
Definition search.cpp:1824
CountingCutoff(std::atomic< unsigned int > &d)
Definition search.cpp:1825
Help class to create and register tests.
Definition search.cpp:1943
Create(void)
Perform creation and registration.
Definition search.cpp:1946
virtual bool run(void)
Run test.
Definition search.cpp:1165
DFS(TestTags tags, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:1157
A search exhausted when it reaches a failure limit is not stopped.
Definition search.cpp:1555
bool run(void) override
Run test.
Definition search.cpp:1594
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:437
IntVarArray x
Variables used.
Definition search.cpp:414
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:416
FailImmediate(FailImmediate &s)
Constructor for cloning s.
Definition search.cpp:422
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:426
static std::string name(void)
Return name.
Definition search.cpp:441
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:433
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:430
Space without solutions whose first portfolio asset fails.
Definition search.cpp:1833
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1837
FailingAsset(FailingAsset &s)
Definition search.cpp:1836
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Definition search.cpp:1840
Space with solutions whose first, incomplete slave fails at the root.
Definition search.cpp:1496
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Definition search.cpp:1503
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1500
FailingFirstSlave(FailingFirstSlave &s)
Definition search.cpp:1499
Space without solutions whose master fails at a restart after a limit.
Definition search.cpp:1390
bool master(const Gecode::MetaInfo &mi) override
Master configuration function for meta search engines.
Definition search.cpp:1397
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1394
FailingMaster(FailingMaster &s)
Definition search.cpp:1393
Space without solutions whose restricted slaves fail at the root.
Definition search.cpp:1438
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1442
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Definition search.cpp:1445
FailingSlave(FailingSlave &s)
Definition search.cpp:1441
Stop after a number of failures, or after many checks as a safeguard.
Definition search.cpp:1541
unsigned long long int limit
Failure limit.
Definition search.cpp:1544
std::atomic< unsigned long int > checks
Number of checks, parallel engines can check concurrently.
Definition search.cpp:1546
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
Definition search.cpp:1548
FailureLimit(unsigned long long int l)
Definition search.cpp:1547
Stop after five failures, or after many checks as a safeguard.
Definition search.cpp:1455
unsigned long int checks
Number of checks.
Definition search.cpp:1458
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
Definition search.cpp:1459
Space that requires propagation and has solutions.
Definition search.cpp:482
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:561
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:524
static std::string name(void)
Return name.
Definition search.cpp:601
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:573
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition search.cpp:528
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
Definition search.cpp:605
HowToConstrain htc
How to constrain.
Definition search.cpp:489
HasSolutions(HasSolutions &s)
Constructor for cloning s.
Definition search.cpp:518
IntVarArray x
Variables used.
Definition search.cpp:485
HowToBranch htb1
How to branch.
Definition search.cpp:487
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition search.cpp:507
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition search.cpp:491
static bool limited(unsigned int threads)
Run width-limited CABS and BAB on a tree where CABS stops early.
Definition search.cpp:326
bool run(void) override
Run test.
Definition search.cpp:306
Heuristic search engines on random trees.
Definition search.cpp:255
Heuristic(const std::string &name)
Definition search.cpp:257
bool run(void) override
Run test.
Definition search.cpp:259
Stop object raising its node limit on each stop.
Definition search.cpp:215
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
Definition search.cpp:220
Increasing(unsigned long long int s)
Definition search.cpp:219
virtual bool run(void)
Run test.
Definition search.cpp:1203
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Definition search.cpp:1197
Space without solutions whose search tree has several failures.
Definition search.cpp:1362
bool master(const Gecode::MetaInfo &mi) override
Master configuration function for meta search engines.
Definition search.cpp:1381
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1375
NoSolution(NoSolution &s)
Definition search.cpp:1372
Gecode::IntVarArray x
Four variables that must be distinct with three values.
Definition search.cpp:1365
Gecode::IntVar cost(void) const override
Return variable with current cost.
Definition search.cpp:1378
The stop object of a portfolio built from builders stops the builders.
Definition search.cpp:1761
bool run(void) override
Run test.
Definition search.cpp:1779
Nested failures must preserve the exception and dispose owned spaces.
Definition search.cpp:706
bool run(void) override
Run test.
Definition search.cpp:748
A portfolio of restart-based assets deletes the cutoff exactly once.
Definition search.cpp:1848
bool run(void) override
Run test.
Definition search.cpp:1870
Restart-based assets of a portfolio share the cutoff sequence.
Definition search.cpp:1791
bool run(void) override
Run test.
Definition search.cpp:1804
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
Definition search.cpp:1640
virtual bool run(void)
Run test.
Definition search.cpp:1644
Track seeds and engine clones through nested construction failures.
Definition search.cpp:690
~PortfolioSeed(void) override
Definition search.cpp:699
PortfolioSeed(PortfolioSeed &s)
Definition search.cpp:695
Space * copy(void) override
Copy during cloning.
Definition search.cpp:698
A failed first slave search that is incomplete is not a proof.
Definition search.cpp:1514
bool run(void) override
Run test.
Definition search.cpp:1531
A master failing at a restart after a limit proves exhaustion.
Definition search.cpp:1406
bool run(void) override
Run test.
Definition search.cpp:1409
No-goods from an incomplete slave search are not posted in the master.
Definition search.cpp:1339
bool run(void) override
Run test.
Definition search.cpp:1342
Slave searches failing at the root count as failures.
Definition search.cpp:1466
bool run(void) override
Run test.
Definition search.cpp:1486
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition search.cpp:1280
virtual bool run(void)
Run test.
Definition search.cpp:1284
Relaxing fails the space when a value cannot be kept.
Definition search.cpp:1612
bool run(void) override
Run test.
Definition search.cpp:1615
Space for relaxing.
Definition search.cpp:1602
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1606
RelaxSpace(RelaxSpace &s)
Definition search.cpp:1605
RelaxSpace(void)=default
Space whose first slave search is restricted to x2, x3 in {0,1}.
Definition search.cpp:1309
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Definition search.cpp:1327
Gecode::IntVarArray x
Distinct variables, the cost is x0.
Definition search.cpp:1312
Gecode::IntVar cost(void) const override
Return variable with current cost.
Definition search.cpp:1324
RestrictedFirstSlave(RestrictedFirstSlave &s)
Definition search.cpp:1317
Gecode::Space * copy(void) override
Copying member function.
Definition search.cpp:1321
Test for portfolio-based search using SEBs
Definition search.cpp:1687
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
Definition search.cpp:1697
virtual bool run(void)
Run test.
Definition search.cpp:1701
Space that is immediately solved.
Definition search.cpp:447
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:468
IntVarArray x
Variables used.
Definition search.cpp:450
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:472
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:460
static std::string name(void)
Return name.
Definition search.cpp:476
SolveImmediate(SolveImmediate &s)
Constructor for cloning s.
Definition search.cpp:456
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:452
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:464
virtual int solutions(void) const =0
Return number of solutions.
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
Definition search.cpp:399
TestSpace(void)
Constructor for space creation.
Definition search.cpp:391
TestSpace(TestSpace &s)
Constructor for cloning s.
Definition search.cpp:393
virtual bool best(void) const =0
Verify that this is best solution.
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition search.cpp:635
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize a normal test.
Definition search.cpp:672
HowToConstrain htc
How to constrain.
Definition search.cpp:633
static std::string str(HowToBranch htb)
Map branching to string.
Definition search.cpp:641
HowToBranch htb1
How to branch.
Definition search.cpp:631
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition search.cpp:653
Test(TestTags tags, const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition search.cpp:666
HowToBranch htb3
Definition search.cpp:631
HowToBranch htb2
Definition search.cpp:631
Brancher choosing a child of the current node.
Definition search.cpp:102
Decisions(Space &home, Decisions &b)
Definition search.cpp:114
Actor * copy(Space &home) override
Create copy.
Definition search.cpp:132
ExecStatus commit(Space &s, const Choice &c, unsigned int a) override
Commit for choice c and alternative a.
Definition search.cpp:127
bool status(const Space &s) const override
Check status of brancher, return true if alternatives left.
Definition search.cpp:115
size_t dispose(Space &home) override
Delete actor and return its size.
Definition search.cpp:135
const Choice * choice(Space &s) override
Return choice.
Definition search.cpp:118
const Choice * choice(const Space &, Archive &e) override
Return choice from e.
Definition search.cpp:123
Explicit finite tree with prefix costs, admissible bounds, and ranks.
Definition search.cpp:90
static Gecode::Search::HeuristicGuidance guidance(bool max, bool ranked, bool dominance, bool keyed)
Guidance minimizing cost, or maximizing negated cost.
Definition search.cpp:157
static std::shared_ptr< const Graph > random(Gecode::Support::RandomGenerator &r, int d=1)
Return a random tree where all nodes above depth d branch.
Definition search.cpp:183
std::shared_ptr< const Graph > graph
Definition search.cpp:98
TreeSpace(TreeSpace &s)
Definition search.cpp:145
const Node & node(void) const
Definition search.cpp:150
Space * copy(void) override
Copying member function.
Definition search.cpp:148
std::vector< Node > Graph
Definition search.cpp:97
bool master(const MetaInfo &) override
Master configuration function for meta search engines.
Definition search.cpp:149
TreeSpace(std::shared_ptr< const Graph > g, bool max)
Definition search.cpp:140
void constrain(const Space &s) override
Constrain function for best solution search.
Definition search.cpp:151
Focused API and binding checks not covered by randomized search.
Definition search.cpp:998
bool run(void) override
Run test.
Definition search.cpp:1012
Requests from other threads while workers search must not lose results.
Definition search.cpp:900
bool run(void) override
Run test.
Definition search.cpp:934
A paused PBS asset must not hold the portfolio round open.
Definition search.cpp:1080
bool run(void) override
Run test.
Definition search.cpp:1084
Pause before search or after its first node, then resume enumeration.
Definition search.cpp:790
bool run(void) override
Run test.
Definition search.cpp:875
Set of test tags.
Definition test.hh:105
static TestTags sweep(void)
Expensive parameter sweeps.
Definition test.hpp:59
static TestTags standard(void)
Standard suite without expensive sweeps.
Definition test.hpp:55
static TestTags check(void)
Integrity tests, also part of the standard suite.
Definition test.hpp:51
const int capacity[n_warehouses]
Capacity of a single warehouse.
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
void fail(void)
Fail space.
Definition core.hpp:4275
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IRT_NQ
Disequality ( ).
Definition int.hh:1227
@ IRT_LE
Less ( ).
Definition int.hh:1229
@ IRT_GR
Greater ( ).
Definition int.hh:1231
@ IRT_LQ
Less or equal ( ).
Definition int.hh:1228
@ BOT_AND
Conjunction.
Definition int.hh:1251
Space(void)
Default constructor.
Definition core.cpp:121
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:896
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition core.cpp:900
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:618
T * bab(T *s, const Search::Options &o=Search::Options::def)
Perform depth-first branch-and-bound search for subclass T of space s and options o.
Definition bab.hpp:77
T * lds(T *s, const Search::Options &o=Search::Options::def)
Invoke limited-discrepancy search for s as root node and optionso.
Definition lds.hpp:74
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:132
Finite domain integers.
Definition lastval.hh:52
Search engines
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
Definition search.hh:1168
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
Definition aliases.hpp:132
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
T * astar(T *s, const Search::Options &o=Search::Options::def)
Perform A* search for subclass T of space s and options o.
Definition astar.hpp:74
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition val.hpp:100
T * cabs(T *s, const Search::Options &o=Search::Options::def)
Perform CABS search for subclass T of space s and options o.
Definition cabs.hpp:74
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
void relax(Home home, const FloatVarArgs &x, const FloatVarArgs &sx, Rnd r, double p)
Definition relax.cpp:57
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
HowToBranch
Values for selecting branchers.
Definition search.cpp:364
@ HTB_BINARY
Branch with two alternatives.
Definition search.cpp:367
@ HTB_NONE
Do not branch.
Definition search.cpp:365
@ HTB_UNARY
Branch with single alternative.
Definition search.cpp:366
@ HTB_NARY
Branch with many alternatives.
Definition search.cpp:368
PBSRestartCutoffDeleted pbs_restart_cutoff_deleted
Definition search.cpp:1886
ExhaustedAtLimit exhausted_at_limit
Definition search.cpp:1599
WorkerControlSequentialPause worker_control_sequential_pause
Definition search.cpp:897
Heuristic< Gecode::CABS > cabs_test("CABS")
RBSFailedMaster rbs_failed_master
Definition search.cpp:1435
WorkerControlConcurrentResize worker_control_concurrent_resize
Definition search.cpp:995
RelaxFailed relax_failed
Definition search.cpp:1626
RBSFailedFirstSlave rbs_failed_first_slave
Definition search.cpp:1538
Heuristic< Gecode::AStar > astar_test("AStar")
RBSRootFailure rbs_root_failure
Definition search.cpp:1493
PBSConstructionFailure pbs_construction_failure
Definition search.cpp:787
HowToConstrain
Values for selecting how to constrain.
Definition search.cpp:372
@ HTC_BAL_GR
Constrain for largest balance.
Definition search.cpp:377
@ HTC_LEX_LE
Constrain for lexically smallest.
Definition search.cpp:374
@ HTC_LEX_GR
Constrain for lexically biggest.
Definition search.cpp:375
@ HTC_BAL_LE
Constrain for smallest balance.
Definition search.cpp:376
@ HTC_NONE
Do not constrain.
Definition search.cpp:373
Test::Search::HeuristicPortfolio heuristic_portfolio
PBSBuilderStop pbs_builder_stop
Definition search.cpp:1788
Gecode::PBS< T, Gecode::RBS > RestartPortfolio
Definition search.cpp:703
WorkerControlPBSPause worker_control_pbs_pause
Definition search.cpp:1143
RBSIncompleteNoGoods rbs_incomplete_nogoods
Definition search.cpp:1359
WorkerControlAPI worker_control_api
Definition search.cpp:1077
WhichModel
Values for selecting models.
Definition search.cpp:381
@ WM_FAIL_SEARCH
Model without solutions.
Definition search.cpp:383
@ WM_SOLUTIONS
Model with solutions.
Definition search.cpp:384
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
Definition search.cpp:382
PBSRestartCutoff pbs_restart_cutoff
Definition search.cpp:1812
General test support.
Definition afc.cpp:41
Region r
Definition region.cpp:65
@ check
Basic integrity tests.
Definition test.hh:99
@ standard
Standard test suite.
Definition test.hh:100
std::vector< int > children
Definition search.cpp:95
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56