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");
74 std::is_copy_constructible<Gecode::Search::WorkerControl>::value,
75 "WorkerControl must remain copy constructible");
77 std::is_copy_assignable<Gecode::Search::WorkerControl>::value,
78 "WorkerControl must remain copy assignable");
88#ifdef GECODE_HAS_EXPERIMENTAL
97 typedef std::vector<Node>
Graph;
98 std::shared_ptr<const Graph>
graph;
103 class Decision :
public Choice {
106 Decision(
const Brancher& b,
int v,
unsigned int n)
108 void archive(
Archive& e)
const override {
120 return new Decision(*
this,t.
vertex,
124 int v;
unsigned int n; e >> v >> n;
125 return new Decision(*
this,v,n);
129 t.
vertex = (*t.
graph)[
static_cast<const Decision&
>(
c).vertex].children[a];
137 return sizeof(*this);
159 HeuristicGuidance g(
max ? HeuristicGuidance::MAXIMIZE :
160 HeuristicGuidance::MINIMIZE,
161 [](
const Space& s) -> std::int64_t {
166 g.
rank = [](
const Space& s) -> std::int64_t {
170 g.dominates = [](
const Space& a,
const Space& b) {
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);
182 static std::shared_ptr<const Graph>
185 g.push_back({0,0,0,0,{}});
187 return std::make_shared<const Graph>(std::move(g));
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);
202 if (g[v].children.empty()) {
203 g[
v].best = g[
v].bound = g[
v].cost;
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)));
216 unsigned long long int limit, step;
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;
237 if (TreeSpace* s = e.next()) {
238 int cost = s->node().cost;
243 }
else if ((stop !=
nullptr) && (stop->stops != stops)) {
250 return e.stopped() || (last == (*root.graph)[0].best);
254 template<
template<
class>
class E>
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;
279 E<TreeSpace> e(&root,o);
280 if (!improving(e,root,step > 0U ? &stop :
nullptr))
299 std::this_thread::sleep_for(std::chrono::microseconds(200));
316#ifdef GECODE_HAS_THREADS
320 if (!improving(e,root))
327#ifndef GECODE_HAS_THREADS
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,{}}
336 TreeSpace root(std::make_shared<const TreeSpace::Graph>(g),
false);
352 int last = std::numeric_limits<int>::max();
354 last = s->node().cost;
357 return (last == 1) && e.
stopped();
397 virtual bool best(
void)
const = 0;
401 if (mi.
last() !=
nullptr)
423 x.update(*
this, s.
x);
437 virtual bool best(
void)
const {
441 static std::string
name(
void) {
457 x.update(*
this, s.
x);
472 virtual bool best(
void)
const {
476 static std::string
name(
void) {
521 x.update(*
this, s.
x);
537 for (
int i=0; i<6; i++)
538 y[i] =
IntVar(*
this, s.
x[i].val(), s.
x[i].val());
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);
573 virtual bool best(
void)
const {
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));
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));
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));
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));
601 static std::string
name(
void) {
608 if (mi.
last() !=
nullptr) {
612 for (
int i=0; i<
x.size(); i++)
613 b <<
expr(*
this,
x[i] == s->
x[i]);
635 static std::string
str(
unsigned int i) {
680 worker_capacity(
unsigned int threads) {
681#ifdef GECODE_HAS_THREADS
707 bool worker_control_failure(
unsigned int threads,
bool clone,
708 bool restart,
bool in_use) {
710 worker_capacity(threads)+1U);
712 std::unique_ptr<Gecode::DFS<SolveImmediate>> binding;
719 std::unique_ptr<PortfolioSeed> root(
new PortfolioSeed(live));
728 std::unique_ptr<Gecode::Search::Cutoff>
744 return caught && (live == (clone ? 1 : 0));
749 for (
unsigned int threads : {1U,4U})
750 for (
bool clone : {
false,
true})
751 for (
int failing : {-1,0,1}) {
753 std::unique_ptr<PortfolioSeed> root(
new PortfolioSeed(live));
774 if (!caught || (live != (clone ? 1 : 0)))
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))
794 std::atomic<bool> paused;
796 std::promise<void> reached;
798 : control(
c), node(n), paused(
false) {}
801 if ((s.
node >= node) && !paused.exchange(
true)) {
808 template<
template<
class>
class E>
809 bool check(
unsigned int node,
unsigned int threads) {
811 Pause pause(control,node);
817 E<HasSolutions> engine(&root,o);
818 auto result = std::async(std::launch::async,[&] {
return engine.next(); });
819 auto reached = pause.reached.get_future();
821 bool ok = result.wait_for(std::chrono::milliseconds(20)) ==
822 std::future_status::timeout;
832 control.request((solutions % 2) ? threads : 1U);
839 return ok && !engine.stopped() && (solutions == root.
solutions());
841#ifdef GECODE_HAS_EXPERIMENTAL
842 template<
template<
class>
class E>
843 bool heuristic(
unsigned int node,
unsigned int threads) {
845 Pause pause(control,node);
854 E<TreeSpace> engine(&root,o);
855 int last = std::numeric_limits<int>::max();
858 last = s->node().cost;
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);
868 return ok && !engine.stopped() && (last == (*root.
graph)[0].best);
874 :
Base(
"Search::WorkerControl::SequentialPause",
TestTags::check()) {}
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))
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))
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;
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();
924 done.store(
true,std::memory_order_release);
925 for (std::thread& resizer : resizers)
927 best = (last !=
nullptr) && last->
best();
929 return !engine.stopped();
933 :
Base(
"Search::WorkerControl::ConcurrentResize",
TestTags::check()) {}
935#ifdef GECODE_HAS_THREADS
937 const unsigned int threads = 4U;
942 WorkerControl control(threads);
947 if (!drain(
dfs,{control},threads,n,best) || (n != root.
solutions()))
952 WorkerControl control(threads);
957 if (!drain(
bab,{control},threads,n,best) || !best)
963 WorkerControl control(threads);
969 if (!drain(
rbs,{control},threads,n,best) || !best ||
970 (
rbs.statistics().restart == 0))
975 WorkerControl controls[2] = {WorkerControl(threads),
976 WorkerControl(threads)};
978 for (
int i=0; i<2; i++) {
987 if (!drain(
pbs,{controls[0],controls[1]},threads,n,best) || !best)
1000 template<
class Exception,
class Function>
1001 static bool throws(Function function) {
1014 WorkerControl empty;
1015 bool ok = !empty.
engaged() && (empty.requested() == 0U) &&
1016 (empty.capacity() == 0U) &&
1017 throws<Gecode::Search::UninitializedWorkerControl>(
1018 [&] { empty.request(1U); });
1020 const unsigned int capacity = worker_capacity(2U);
1021 WorkerControl control(0U);
1022 WorkerControl copy(control);
1024 ok = ok && copy.engaged() && (copy.requested() == 0U);
1031#ifndef GECODE_HAS_THREADS
1032 ok = ok && throws<Gecode::Search::InvalidWorkerRequest>(
1034 control.request(1U);
1035 ok = ok && throws<Gecode::Search::InvalidWorkerRequest>(
1036 [&] { control.request(0U); });
1042 ok = ok && (control.capacity() ==
capacity);
1043 ok = ok && throws<Gecode::Search::WorkerControlInUse>([&] {
1046 control.request(1U);
1047 ok = ok && (copy.requested() == 1U) &&
1048 throws<Gecode::Search::InvalidWorkerRequest>(
1049 [&] { control.request(
capacity+1U); });
1050 delete engine.
next();
1053 ok = ok && throws<Gecode::Search::WorkerControlInUse>(
1058#ifdef GECODE_HAS_THREADS
1060 ok = ok && (control.requested() == 0U);
1062 ok = ok && (control.capacity() ==
capacity) &&
1063 throws<Gecode::Search::InvalidWorkerRequest>([&] {
1071 delete engine.
next();
1083 :
Base(
"Search::WorkerControl::PBS::Pause",
TestTags::check()) {}
1087 for (
unsigned int requested : {0U,1U}) {
1096 bool rejected =
false;
1104 ok = ok && rejected;
1106#ifdef GECODE_HAS_THREADS
1107 for (
unsigned int threads : {1U,2U})
1108 for (
bool restart : {
false,
true}) {
1111 paused_options.
threads = threads;
1127 portfolio_options.
threads = 2.0;
1131 pbs(root,sebs,portfolio_options);
1135 ok = ok && (solution !=
nullptr) && (paused.
requested() == 0U);
1146 template<
class Model>
1159 unsigned int c_d0,
unsigned int a_d0,
unsigned int t0)
1174 int n = m->solutions();
1177 Model* s =
dfs.next();
1181 if ((s ==
nullptr) && !
dfs.stopped())
1183 f.limit(f.limit()+2);
1190 template<
class Model>
1211 int n = m->solutions();
1214 Model* s =
lds.next();
1218 if ((s ==
nullptr) && !
lds.stopped())
1220 f.limit(f.limit()+2);
1227 template<
class Model>
1240 unsigned int c_d0,
unsigned int a_d0,
unsigned int t0)
1258 Model* s =
bab.next();
1262 if ((s ==
nullptr) && !
bab.stopped())
1264 f.limit(f.limit()+2);
1266 bool ok = (b ==
nullptr) || b->best();
1273 template<
class Model,
template<
class>
class Engine>
1280 RBS(
const std::string& e,
unsigned int t0)
1293 int n = m->solutions();
1296 Model* s =
rbs.next();
1300 if ((s ==
nullptr) && !
rbs.stopped())
1302 f.limit(f.limit()+2);
1319 x.update(*
this,s.
x);
1352 best = s->x[0].val();
1355 return !
rbs.stopped() && (best == 0);
1367 for (
int i=0; i<
x.size(); i++)
1368 for (
int j=i+1; j<
x.size(); j++)
1373 x.update(*
this,s.
x);
1410 for (
unsigned int t : {1U,2U}) {
1424 ((t == 1U) && (s.
fail != 2U)))
1426 if ((
rbs.next() !=
nullptr) ||
rbs.stopped() ||
1427 (
rbs.statistics().fail != s.
fail) ||
1428 (
rbs.statistics().node != s.
node))
1467 template<
template<
class>
class Engine>
1468 static bool test(
unsigned int threads) {
1481 return rbs.stopped() && (f.checks <= 1000) &&
1482 (
rbs.statistics().fail >= 5);
1487 return test<Gecode::DFS>(1U) && test<Gecode::DFS>(2U) &&
1488 test<Gecode::BAB>(1U) && test<Gecode::BAB>(2U) &&
1489 test<Gecode::LDS>(1U);
1515 template<
template<
class>
class Engine>
1516 static bool test(
unsigned int threads) {
1527 return rbs.statistics().restart >= 1U;
1532 return test<Gecode::DFS>(1U) && test<Gecode::DFS>(2U) &&
1533 test<Gecode::BAB>(1U) && test<Gecode::BAB>(2U) &&
1534 test<Gecode::LDS>(1U);
1556 template<
template<
class>
class Engine>
1557 static bool test(
void) {
1559 unsigned long long int f;
1561 Engine<NoSolution> e(&root);
1566 f = e.statistics().fail;
1575 Engine<NoSolution> e(&root,o);
1576 if ((e.next() !=
nullptr) || e.stopped())
1587 if ((
rbs.next() !=
nullptr) ||
rbs.stopped())
1595 return test<Gecode::DFS>() && test<Gecode::BAB>();
1629 template<
class Model,
template<
class>
class Engine>
1640 PBS(
const std::string& e,
bool b,
unsigned int a0,
unsigned int t0)
1657 Model* s =
pbs.next();
1661 if ((s ==
nullptr) && !
pbs.stopped())
1663 f.limit(f.limit()+2);
1665 bool ok = (b ==
nullptr) || b->best();
1669 int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
1672 Model* s =
pbs.next();
1676 if ((s ==
nullptr) && !
pbs.stopped())
1678 f.limit(f.limit()+2);
1686 template<
class Model>
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),
1725 Model* s =
pbs.next();
1729 if ((s ==
nullptr) && !
pbs.stopped())
1731 f.limit(f.limit()+2);
1733 bool ok = (b ==
nullptr) || b->best();
1743 int n = 3 * m->solutions();
1747 Model* s =
pbs.next();
1751 if ((s ==
nullptr) && !
pbs.stopped())
1753 f.limit(f.limit()+2);
1764 template<
template<
class>
class Engine>
1765 static bool test(
unsigned int threads, Builder builder) {
1775 return (
pbs.next() ==
nullptr) &&
pbs.stopped() && (l.
checks <= 1000);
1780 for (
unsigned int t : {1U,2U})
1792 template<
template<
class>
class Engine>
1793 static bool test(
unsigned int threads) {
1800 return (
pbs.next() ==
nullptr) && !
pbs.stopped();
1805 for (
unsigned int t : {1U,2U,4U})
1806 if (!test<Gecode::RBS>(t) || !test<RestartPortfolio>(t))
1849 template<
class Root,
template<
class>
class Engine>
1850 static bool test(Root& root,
unsigned int threads) {
1851 std::atomic<unsigned int> deleted{0U};
1858 if (Root* s =
pbs.next()) {
1865 return deleted == 1U;
1869 :
Base(
"Search::PBS::RBS::CutoffDeleted") {}
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))
1912 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
1938 const HowToConstrain ConstrainTypes::htcs[4] =
1939 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
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++) {
1958 (c_d == 1) && (a_d == 1) && (t == 1)
1961 htb1.htb(),htb2.htb(),htb3.htb(),c_d,a_d,t);
1974 for (
unsigned int t = 1; t<=4; t++) {
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++) {
1997 (c_d == 1) && (a_d == 1) && (t == 1)
2000 htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
2014 for (
unsigned int t=1; t<=4; t++) {
2026 for (
unsigned int a=1; a<=4; a++)
2027 for (
unsigned int t=1; t<=2*a; t++) {
2039 for (
unsigned int mt=1; mt<=3; mt += 2)
2040 for (
unsigned int st=1; st<=8; st++) {
virtual size_t dispose(Space &home)
Delete actor and return its size.
Depth-first branch-and-bound search engine.
Passing Boolean variables.
Brancher(Home home)
Constructor for creation.
virtual void archive(Archive &e) const
Archive into e.
unsigned int alternatives(void) const
Return number of alternatives.
Depth-first search engine.
Exception: Base-class for exceptions
Home class for posting propagators
Class for minimizing integer cost.
IntMinimizeSpace(void)
Default constructor.
Passing integer variables.
Limited discrepancy search engine.
Meta engine using a portfolio of search engines.
Meta-engine performing restart-based search.
Passing search engine builder arguments.
virtual bool stopped(void) const
Check whether engine has been stopped.
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Cutoff generator for constant sequence.
CutoffConstant(unsigned long long int c)
Constructor.
static Cutoff * constant(unsigned long long int scale=Config::slice)
Create generator for constant sequence with constant s.
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Stop-object based on number of failures
Guidance for heuristic search engines (experimental).
Evaluate rank
Node rank (optional, lower first).
Exception: Invalid requested number of search workers
static const Options def
Default options.
unsigned int c_d
Create a clone after every c_d commits (commit distance).
WorkerControl worker_control
bool clone
Whether engines create a clone when being initialized.
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
unsigned int d_l
Discrepancy limit (for LDS, reaching it does not stop the engine).
Cutoff * cutoff
Cutoff for restart-based search.
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Stop * stop
Stop object for stopping search.
unsigned long int max_width
Maximal beam width for CABS (zero for no limit).
unsigned int assets
Number of assets (engines) in a portfolio.
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
double threads
Number of threads to use.
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.
Base-class for Stop-object.
Exception: Uninitialized cutoff for restart-based search
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
External control for the requested number of search workers.
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).
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Gecode::Support::RandomGenerator _rand
Random number generator.
Base(std::string s)
Create and register a standard test with name s.
const std::string & name(void) const
Return name of test.
TestTags tags(void) const
Return tags for test.
BAB(TestTags tags, HowToConstrain htc, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
virtual bool run(void)
Run test.
Iterator for branching types.
HowToBranch htb(void) const
Return current branching type.
BranchTypes(void)
Initialize iterator.
void operator++(void)
Increment to next branching type.
bool operator()(void) const
Test whether iterator is done.
Iterator for constrain types.
HowToConstrain htc(void) const
Return current constrain type.
void operator++(void)
Increment to next constrain type.
bool operator()(void) const
Test whether iterator is done.
ConstrainTypes(void)
Initialize iterator.
Constant cutoff counting its deletions.
~CountingCutoff(void) override
std::atomic< unsigned int > & deleted
Number of deletions, owned by the test.
CountingCutoff(std::atomic< unsigned int > &d)
Help class to create and register tests.
Create(void)
Perform creation and registration.
virtual bool run(void)
Run test.
DFS(TestTags tags, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
A search exhausted when it reaches a failure limit is not stopped.
bool run(void) override
Run test.
Space without solutions whose first portfolio asset fails.
Gecode::Space * copy(void) override
Copying member function.
FailingAsset(void)=default
FailingAsset(FailingAsset &s)
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Space with solutions whose first, incomplete slave fails at the root.
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
FailingFirstSlave(void)=default
Gecode::Space * copy(void) override
Copying member function.
FailingFirstSlave(FailingFirstSlave &s)
Space without solutions whose master fails at a restart after a limit.
bool master(const Gecode::MetaInfo &mi) override
Master configuration function for meta search engines.
FailingMaster(void)=default
Gecode::Space * copy(void) override
Copying member function.
FailingMaster(FailingMaster &s)
Space without solutions whose restricted slaves fail at the root.
FailingSlave(void)=default
Gecode::Space * copy(void) override
Copying member function.
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
FailingSlave(FailingSlave &s)
Stop after a number of failures, or after many checks as a safeguard.
unsigned long long int limit
Failure limit.
std::atomic< unsigned long int > checks
Number of checks, parallel engines can check concurrently.
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
FailureLimit(unsigned long long int l)
Stop after five failures, or after many checks as a safeguard.
unsigned long int checks
Number of checks.
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
Space that requires propagation and has solutions.
virtual int solutions(void) const
Return number of solutions.
virtual Space * copy(void)
Copy during cloning.
static std::string name(void)
Return name.
virtual bool best(void) const
Verify that this is best solution.
virtual void constrain(const Space &_s)
Add constraint for next better solution.
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
HowToConstrain htc
How to constrain.
HasSolutions(HasSolutions &s)
Constructor for cloning s.
IntVarArray x
Variables used.
HowToBranch htb1
How to branch.
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
static bool limited(unsigned int threads)
Run width-limited CABS and BAB on a tree where CABS stops early.
bool run(void) override
Run test.
Heuristic search engines on random trees.
Heuristic(const std::string &name)
bool run(void) override
Run test.
Stop object raising its node limit on each stop.
bool stop(const Gecode::Search::Statistics &s, const Gecode::Search::Options &) override
Stop search, if returns true.
Increasing(unsigned long long int s)
virtual bool run(void)
Run test.
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Space without solutions whose search tree has several failures.
bool master(const Gecode::MetaInfo &mi) override
Master configuration function for meta search engines.
Gecode::Space * copy(void) override
Copying member function.
NoSolution(NoSolution &s)
Gecode::IntVarArray x
Four variables that must be distinct with three values.
Gecode::IntVar cost(void) const override
Return variable with current cost.
The stop object of a portfolio built from builders stops the builders.
bool run(void) override
Run test.
Nested failures must preserve the exception and dispose owned spaces.
bool run(void) override
Run test.
PBSConstructionFailure(void)
A portfolio of restart-based assets deletes the cutoff exactly once.
bool run(void) override
Run test.
PBSRestartCutoffDeleted(void)
Restart-based assets of a portfolio share the cutoff sequence.
bool run(void) override
Run test.
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
virtual bool run(void)
Run test.
Track seeds and engine clones through nested construction failures.
~PortfolioSeed(void) override
PortfolioSeed(int &count)
PortfolioSeed(PortfolioSeed &s)
Space * copy(void) override
Copy during cloning.
A failed first slave search that is incomplete is not a proof.
bool run(void) override
Run test.
RBSFailedFirstSlave(void)
A master failing at a restart after a limit proves exhaustion.
bool run(void) override
Run test.
No-goods from an incomplete slave search are not posted in the master.
bool run(void) override
Run test.
RBSIncompleteNoGoods(void)
Slave searches failing at the root count as failures.
bool run(void) override
Run test.
RBS(const std::string &e, unsigned int t0)
Initialize test.
virtual bool run(void)
Run test.
Relaxing fails the space when a value cannot be kept.
bool run(void) override
Run test.
Gecode::Space * copy(void) override
Copying member function.
RelaxSpace(RelaxSpace &s)
Space whose first slave search is restricted to x2, x3 in {0,1}.
bool slave(const Gecode::MetaInfo &mi) override
Slave configuration function for meta search engines.
Gecode::IntVarArray x
Distinct variables, the cost is x0.
RestrictedFirstSlave(void)
Gecode::IntVar cost(void) const override
Return variable with current cost.
RestrictedFirstSlave(RestrictedFirstSlave &s)
Gecode::Space * copy(void) override
Copying member function.
Test for portfolio-based search using SEBs
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
virtual bool run(void)
Run test.
virtual int solutions(void) const =0
Return number of solutions.
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
TestSpace(void)
Constructor for space creation.
TestSpace(TestSpace &s)
Constructor for cloning s.
virtual bool best(void) const =0
Verify that this is best solution.
static std::string str(unsigned int i)
Map unsigned integer to string.
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize a normal test.
HowToConstrain htc
How to constrain.
static std::string str(HowToBranch htb)
Map branching to string.
HowToBranch htb1
How to branch.
static std::string str(HowToConstrain htc)
Map constrain to string.
Test(TestTags tags, const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Brancher choosing a child of the current node.
Decisions(Space &home, Decisions &b)
Actor * copy(Space &home) override
Create copy.
ExecStatus commit(Space &s, const Choice &c, unsigned int a) override
Commit for choice c and alternative a.
bool status(const Space &s) const override
Check status of brancher, return true if alternatives left.
size_t dispose(Space &home) override
Delete actor and return its size.
const Choice * choice(Space &s) override
Return choice.
const Choice * choice(const Space &, Archive &e) override
Return choice from e.
Explicit finite tree with prefix costs, admissible bounds, and ranks.
static Gecode::Search::HeuristicGuidance guidance(bool max, bool ranked, bool dominance, bool keyed)
Guidance minimizing cost, or maximizing negated cost.
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.
std::shared_ptr< const Graph > graph
const Node & node(void) const
Space * copy(void) override
Copying member function.
std::vector< Node > Graph
bool master(const MetaInfo &) override
Master configuration function for meta search engines.
TreeSpace(std::shared_ptr< const Graph > g, bool max)
void constrain(const Space &s) override
Constrain function for best solution search.
Focused API and binding checks not covered by randomized search.
bool run(void) override
Run test.
Requests from other threads while workers search must not lose results.
WorkerControlConcurrentResize(void)
bool run(void) override
Run test.
A paused PBS asset must not hold the portfolio round open.
bool run(void) override
Run test.
WorkerControlPBSPause(void)
Pause before search or after its first node, then resume enumeration.
bool run(void) override
Run test.
WorkerControlSequentialPause(void)
const int capacity[n_warehouses]
Capacity of a single warehouse.
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
bool failed(void) const
Check whether space is failed.
void fail(void)
Fail space.
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.
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.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
@ IRT_LQ
Less or equal ( ).
Space(void)
Default constructor.
virtual void constrain(const Space &best)
Constrain function for best solution search.
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
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.
T * lds(T *s, const Search::Options &o=Search::Options::def)
Invoke limited-discrepancy search for s as root node and optionso.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
T * astar(T *s, const Search::Options &o=Search::Options::def)
Perform A* search for subclass T of space s and options o.
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
T * cabs(T *s, const Search::Options &o=Search::Options::def)
Perform CABS search for subclass T of space s and options o.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
void relax(Home home, const FloatVarArgs &x, const FloatVarArgs &sx, Rnd r, double p)
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.
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
@ ES_OK
Execution is okay.
@ ES_FAILED
Execution has resulted in failure.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
HowToBranch
Values for selecting branchers.
@ HTB_BINARY
Branch with two alternatives.
@ HTB_UNARY
Branch with single alternative.
@ HTB_NARY
Branch with many alternatives.
PBSRestartCutoffDeleted pbs_restart_cutoff_deleted
ExhaustedAtLimit exhausted_at_limit
WorkerControlSequentialPause worker_control_sequential_pause
Heuristic< Gecode::CABS > cabs_test("CABS")
RBSFailedMaster rbs_failed_master
WorkerControlConcurrentResize worker_control_concurrent_resize
RBSFailedFirstSlave rbs_failed_first_slave
Heuristic< Gecode::AStar > astar_test("AStar")
RBSRootFailure rbs_root_failure
PBSConstructionFailure pbs_construction_failure
HowToConstrain
Values for selecting how to constrain.
@ HTC_BAL_GR
Constrain for largest balance.
@ HTC_LEX_LE
Constrain for lexically smallest.
@ HTC_LEX_GR
Constrain for lexically biggest.
@ HTC_BAL_LE
Constrain for smallest balance.
@ HTC_NONE
Do not constrain.
Test::Search::HeuristicPortfolio heuristic_portfolio
PBSBuilderStop pbs_builder_stop
Gecode::PBS< T, Gecode::RBS > RestartPortfolio
WorkerControlPBSPause worker_control_pbs_pause
RBSIncompleteNoGoods rbs_incomplete_nogoods
WorkerControlAPI worker_control_api
WhichModel
Values for selecting models.
@ WM_FAIL_SEARCH
Model without solutions.
@ WM_SOLUTIONS
Model with solutions.
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
PBSRestartCutoff pbs_restart_cutoff
@ check
Basic integrity tests.
@ standard
Standard test suite.
std::vector< int > children
#define GECODE_NEVER
Assert that this command is never executed.