search.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2008
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/minimodel.hh>
#include <gecode/search.hh>
#include "test/test.hh"
namespace Test {
namespace Search {
using namespace Gecode;
using namespace Gecode::Int;
enum HowToBranch {
HTB_NONE,
HTB_UNARY,
HTB_BINARY,
HTB_NARY
};
enum HowToConstrain {
HTC_NONE,
HTC_LEX_LE,
HTC_LEX_GR,
HTC_BAL_LE,
HTC_BAL_GR
};
enum WhichModel {
WM_FAIL_IMMEDIATE,
WM_FAIL_SEARCH,
WM_SOLUTIONS
};
class TestSpace : public Space {
public:
TestSpace(void) {}
TestSpace(TestSpace& s) : Space(s) {}
virtual int solutions(void) const = 0;
virtual bool best(void) const = 0;
virtual bool master(const MetaInfo& mi) {
if (mi.type() == MetaInfo::RESTART) {
if (mi.last() != NULL)
constrain(*mi.last());
return false;
} else {
return false;
}
}
};
class FailImmediate : public TestSpace {
public:
IntVarArray x;
FailImmediate(HowToBranch, HowToBranch, HowToBranch,
HowToConstrain=HTC_NONE)
: x(*this,1,0,0) {
rel(*this, x[0], IRT_EQ, 1);
}
FailImmediate(FailImmediate& s) : TestSpace(s) {
x.update(*this, s.x);
}
virtual Space* copy(void) {
return new FailImmediate(*this);
}
virtual void constrain(const Space&) {
}
virtual int solutions(void) const {
return 0;
}
virtual bool best(void) const {
return false;
}
static std::string name(void) {
return "Fail";
}
};
class SolveImmediate : public TestSpace {
public:
IntVarArray x;
SolveImmediate(HowToBranch, HowToBranch, HowToBranch,
HowToConstrain=HTC_NONE)
: x(*this,1,0,0) {}
SolveImmediate(SolveImmediate& s) : TestSpace(s) {
x.update(*this, s.x);
}
virtual Space* copy(void) {
return new SolveImmediate(*this);
}
virtual void constrain(const Space&) {
fail();
}
virtual int solutions(void) const {
return 1;
}
virtual bool best(void) const {
return true;
}
static std::string name(void) {
return "Solve";
}
};
class HasSolutions : public TestSpace {
public:
IntVarArray x;
HowToBranch htb1, htb2, htb3;
HowToConstrain htc;
void branch(const IntVarArgs& x, HowToBranch htb) {
switch (htb) {
case HTB_NONE:
break;
case HTB_UNARY:
assign(*this, x, INT_ASSIGN_MIN());
break;
case HTB_BINARY:
Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
break;
case HTB_NARY:
Gecode::branch(*this, x, INT_VAR_NONE(), INT_VALUES_MIN());
break;
}
}
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
HowToConstrain _htc=HTC_NONE)
: x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
distinct(*this, x);
rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
}
HasSolutions(HasSolutions& s)
: TestSpace(s),
htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
x.update(*this, s.x);
}
virtual Space* copy(void) {
return new HasSolutions(*this);
}
virtual void constrain(const Space& _s) {
const HasSolutions& s = static_cast<const HasSolutions&>(_s);
switch (htc) {
case HTC_NONE:
break;
case HTC_LEX_LE:
case HTC_LEX_GR:
{
IntVarArgs y(6);
for (int i=0; i<6; i++)
y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
break;
}
case HTC_BAL_LE:
case HTC_BAL_GR:
{
IntVarArgs y(6);
for (int i=0; i<6; i++)
y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
IntVar xs(*this, -18, 18);
IntVar ys(*this, -18, 18);
rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
rel(*this,
expr(*this,abs(xs)),
(htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
expr(*this,abs(ys)));
break;
}
}
}
virtual int solutions(void) const {
if (htb1 == HTB_NONE) {
assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
return 1;
}
if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
return 0;
if (htb3 == HTB_UNARY)
return 4;
return 8;
}
virtual bool best(void) const {
if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
(htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
return true;
switch (htc) {
case HTC_NONE:
return true;
case HTC_LEX_LE:
return ((x[0].val()==4) && (x[1].val()==5) &&
(x[2].val()==2) && (x[3].val()==3) &&
(x[4].val()==0) && (x[5].val()==1));
case HTC_LEX_GR:
return ((x[0].val()==5) && (x[1].val()==4) &&
(x[2].val()==3) && (x[3].val()==2) &&
(x[4].val()==1) && (x[5].val()==0));
case HTC_BAL_LE:
return ((x[0].val()==4) && (x[1].val()==5) &&
(x[2].val()==2) && (x[3].val()==3) &&
(x[4].val()==0) && (x[5].val()==1));
case HTC_BAL_GR:
return ((x[0].val()==4) && (x[1].val()==5) &&
(x[2].val()==3) && (x[3].val()==2) &&
(x[4].val()==0) && (x[5].val()==1));
default: GECODE_NEVER;
}
return false;
}
static std::string name(void) {
return "Sol";
}
virtual bool master(const MetaInfo& mi) {
switch (mi.type()) {
case MetaInfo::RESTART:
if (mi.last() != NULL) {
const HasSolutions* s
= static_cast<const HasSolutions*>(mi.last());
BoolVarArgs b;
for (int i=0; i<x.size(); i++)
b << expr(*this, x[i] == s->x[i]);
rel(*this, BOT_AND, b, 0);
}
break;
case MetaInfo::PORTFOLIO:
// Do not kill the brancher!
break;
default:
break;
}
return false;
}
};
class Test : public Base {
public:
HowToBranch htb1, htb2, htb3;
HowToConstrain htc;
static std::string str(unsigned int i) {
std::stringstream s;
s << i;
return s.str();
}
static std::string str(HowToBranch htb) {
switch (htb) {
case HTB_NONE: return "None";
case HTB_UNARY: return "Unary";
case HTB_BINARY: return "Binary";
case HTB_NARY: return "Nary";
default: GECODE_NEVER;
}
GECODE_NEVER;
return "";
}
static std::string str(HowToConstrain htc) {
switch (htc) {
case HTC_NONE: return "None";
case HTC_LEX_LE: return "LexLe";
case HTC_LEX_GR: return "LexGr";
case HTC_BAL_LE: return "BalLe";
case HTC_BAL_GR: return "BalGr";
default: GECODE_NEVER;
}
GECODE_NEVER;
return "";
}
Test(const std::string& s,
HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
HowToConstrain _htc=HTC_NONE)
: Base("Search::"+s),
htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
};
template<class Model>
class DFS : public Test {
private:
unsigned int c_d;
unsigned int a_d;
unsigned int t;
public:
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
unsigned int c_d0, unsigned int a_d0, unsigned int t0)
: Test("DFS::"+Model::name()+"::"+
str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
virtual bool run(void) {
Model* m = new Model(htb1,htb2,htb3);
Gecode::Search::FailStop f(2);
Gecode::Search::Options o;
o.c_d = c_d;
o.a_d = a_d;
o.threads = t;
o.stop = &f;
Gecode::DFS<Model> dfs(m,o);
int n = m->solutions();
delete m;
while (true) {
Model* s = dfs.next();
if (s != NULL) {
n--; delete s;
}
if ((s == NULL) && !dfs.stopped())
break;
f.limit(f.limit()+2);
}
return n == 0;
}
};
template<class Model>
class LDS : public Test {
private:
unsigned int t;
public:
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
unsigned int t0)
: Test("LDS::"+Model::name()+"::"+
str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
htb1,htb2,htb3), t(t0) {}
virtual bool run(void) {
Model* m = new Model(htb1,htb2,htb3);
Gecode::Search::FailStop f(2);
Gecode::Search::Options o;
o.threads = t;
o.d_l = 50;
o.stop = &f;
Gecode::LDS<Model> lds(m,o);
int n = m->solutions();
delete m;
while (true) {
Model* s = lds.next();
if (s != NULL) {
n--; delete s;
}
if ((s == NULL) && !lds.stopped())
break;
f.limit(f.limit()+2);
}
return n == 0;
}
};
template<class Model>
class BAB : public Test {
private:
unsigned int c_d;
unsigned int a_d;
unsigned int t;
public:
BAB(HowToConstrain htc,
HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
unsigned int c_d0, unsigned int a_d0, unsigned int t0)
: Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
virtual bool run(void) {
Model* m = new Model(htb1,htb2,htb3,htc);
Gecode::Search::FailStop f(2);
Gecode::Search::Options o;
o.c_d = c_d;
o.a_d = a_d;
o.threads = t;
o.stop = &f;
Gecode::BAB<Model> bab(m,o);
delete m;
Model* b = NULL;
while (true) {
Model* s = bab.next();
if (s != NULL) {
delete b; b=s;
}
if ((s == NULL) && !bab.stopped())
break;
f.limit(f.limit()+2);
}
bool ok = (b == NULL) || b->best();
delete b;
return ok;
}
};
template<class Model, template<class> class Engine>
class RBS : public Test {
private:
unsigned int t;
public:
RBS(const std::string& e, unsigned int t0)
: Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
HTB_BINARY,HTB_BINARY,HTB_BINARY), t(t0) {}
virtual bool run(void) {
Model* m = new Model(htb1,htb2,htb3);
Gecode::Search::FailStop f(2);
Gecode::Search::Options o;
o.threads = t;
o.stop = &f;
o.d_l = 100;
o.cutoff = Gecode::Search::Cutoff::geometric(1,2);
Gecode::RBS<Model,Engine> rbs(m,o);
int n = m->solutions();
delete m;
while (true) {
Model* s = rbs.next();
if (s != NULL) {
n--; delete s;
}
if ((s == NULL) && !rbs.stopped())
break;
f.limit(f.limit()+2);
}
return n == 0;
}
};
template<class Model, template<class> class Engine>
class PBS : public Test {
private:
bool best;
unsigned int a;
unsigned int t;
public:
PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
: Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
virtual bool run(void) {
Model* m = new Model(htb1,htb2,htb3);
Gecode::Search::FailStop f(2);
Gecode::Search::Options o;
o.assets = a;
o.threads = t;
o.d_l = 100;
o.stop = &f;
Gecode::PBS<Model,Engine> pbs(m,o);
if (best) {
Model* b = NULL;
while (true) {
Model* s = pbs.next();
if (s != NULL) {
delete b; b=s;
}
if ((s == NULL) && !pbs.stopped())
break;
f.limit(f.limit()+2);
}
bool ok = (b == NULL) || b->best();
delete b;
return ok;
} else {
int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
delete m;
while (true) {
Model* s = pbs.next();
if (s != NULL) {
n--; delete s;
}
if ((s == NULL) && !pbs.stopped())
break;
f.limit(f.limit()+2);
}
return n >= 0;
}
}
};
template<class Model>
class SEBPBS : public Test {
private:
bool best;
unsigned int mt;
unsigned int st;
public:
SEBPBS(const std::string& e, bool b, unsigned int mt0, unsigned int st0)
: Test("PBS::SEB::"+e+"::"+Model::name()+"::"+str(mt0)+"::"+str(st0),
HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
virtual bool run(void) {
using namespace Gecode;
Model* m = new Model(htb1,htb2,htb3);
Gecode::Search::FailStop f(2);
Gecode::Search::Options mo;
mo.threads = mt;
mo.d_l = 100;
mo.stop = &f;
Gecode::Search::Options so;
so.threads = st;
so.d_l = 100;
so.cutoff = Gecode::Search::Cutoff::constant(1000000);
if (best) {
SEBs sebs(3);
sebs[0] = bab<Model>(so);
sebs[1] = bab<Model>(so);
sebs[2] = rbs<Model,Gecode::BAB>(so);
Gecode::PBS<Model,Gecode::BAB> pbs(m, sebs, mo);
delete m;
Model* b = NULL;
while (true) {
Model* s = pbs.next();
if (s != NULL) {
delete b; b=s;
}
if ((s == NULL) && !pbs.stopped())
break;
f.limit(f.limit()+2);
}
bool ok = (b == NULL) || b->best();
delete b;
return ok;
} else {
SEBs sebs(3);
sebs[0] = dfs<Model>(so);
sebs[1] = lds<Model>(so);
sebs[2] = rbs<Model,Gecode::DFS>(so);
Gecode::PBS<Model,Gecode::DFS> pbs(m, sebs, mo);
int n = 3 * m->solutions();
delete m;
while (true) {
Model* s = pbs.next();
if (s != NULL) {
n--; delete s;
}
if ((s == NULL) && !pbs.stopped())
break;
f.limit(f.limit()+2);
}
return n >= 0;
}
}
};
class BranchTypes {
private:
static const HowToBranch htbs[3];
int i;
public:
BranchTypes(void) : i(0) {}
bool operator()(void) const {
return i<3;
}
void operator++(void) {
i++;
}
HowToBranch htb(void) const {
return htbs[i];
}
};
const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
class ConstrainTypes {
private:
static const HowToConstrain htcs[4];
int i;
public:
ConstrainTypes(void) : i(0) {}
bool operator()(void) const {
return i<4;
}
void operator++(void) {
i++;
}
HowToConstrain htc(void) const {
return htcs[i];
}
};
const HowToConstrain ConstrainTypes::htcs[4] =
{HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
class Create {
public:
Create(void) {
// Depth-first search
for (unsigned int t = 1; t<=4; t++)
for (unsigned int c_d = 1; c_d<10; c_d++)
for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
for (BranchTypes htb1; htb1(); ++htb1)
for (BranchTypes htb2; htb2(); ++htb2)
for (BranchTypes htb3; htb3(); ++htb3)
(void) new DFS<HasSolutions>
(htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
c_d, a_d, t);
new DFS<SolveImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
c_d, a_d, t);
new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
c_d, a_d, t);
}
// Limited discrepancy search
for (unsigned int t = 1; t<=4; t++) {
for (BranchTypes htb1; htb1(); ++htb1)
for (BranchTypes htb2; htb2(); ++htb2)
for (BranchTypes htb3; htb3(); ++htb3)
(void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
,t);
new LDS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE, t);
new LDS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE, t);
}
// Best solution search
for (unsigned int t = 1; t<=4; t++)
for (unsigned int c_d = 1; c_d<10; c_d++)
for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
for (ConstrainTypes htc; htc(); ++htc)
for (BranchTypes htb1; htb1(); ++htb1)
for (BranchTypes htb2; htb2(); ++htb2)
for (BranchTypes htb3; htb3(); ++htb3) {
(void) new BAB<HasSolutions>
(htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
c_d,a_d,t);
}
(void) new BAB<FailImmediate>
(HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
(void) new BAB<SolveImmediate>
(HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
(void) new BAB<HasSolutions>
(HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
}
// Restart-based search
for (unsigned int t=1; t<=4; t++) {
(void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
(void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
(void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
(void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
(void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
(void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
(void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
(void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
(void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
}
// Portfolio-based search
for (unsigned int a=1; a<=4; a++)
for (unsigned int t=1; t<=2*a; t++) {
(void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
(void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
(void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
(void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
(void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
(void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
(void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
(void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
(void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
}
// Portfolio-based search using SEBs
for (unsigned int mt=1; mt<=3; mt += 2)
for (unsigned int st=1; st<=8; st++) {
(void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
(void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
(void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
(void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
(void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
(void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
}
}
};
Create c;
}
}
// STATISTICS: test-search
Gecode::BAB
Depth-first branch-and-bound search engine.
Definition search.hh:1070
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::DFS
Depth-first search engine.
Definition search.hh:1036
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::LDS
Limited discrepancy search engine.
Definition search.hh:1108
Gecode::MetaInfo
Information passed by meta search engines.
Definition core.hpp:1613
Gecode::MetaInfo::PORTFOLIO
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1620
Gecode::MetaInfo::RESTART
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1618
Gecode::MetaInfo::last
const Space * last(void) const
Return last solution found (possibly NULL).
Definition core.hpp:3101
Gecode::MetaInfo::type
Type type(void) const
Return type of information.
Definition core.hpp:3082
Gecode::PBS
Meta engine using a portfolio of search engines.
Definition search.hh:1236
Gecode::RBS
Meta-engine performing restart-based search.
Definition search.hh:1152
Gecode::SEBs
Passing search engine builder arguments.
Definition search.hh:1002
Gecode::Search::Cutoff::geometric
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
Gecode::Search::Cutoff::constant
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition cutoff.cpp:148
Gecode::Search::FailStop
Stop-object based on number of failures
Definition search.hh:852
Gecode::Search::Options
Search engine options
Definition search.hh:746
Gecode::Search::Options::c_d
unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:753
Gecode::Search::Options::d_l
unsigned int d_l
Discrepancy limit (for LDS).
Definition search.hh:757
Gecode::Search::Options::cutoff
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:767
Gecode::Search::Options::a_d
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:755
Gecode::Search::Options::stop
Stop * stop
Stop object for stopping search.
Definition search.hh:765
Gecode::Search::Options::assets
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:759
Gecode::Search::Options::threads
double threads
Number of threads to use.
Definition search.hh:751
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Base::Base
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Test::Base::name
const std::string & name(void) const
Return name of test.
Definition test.hpp:50
Test::Search::BAB::BAB
BAB(HowToConstrain htc, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:449
Test::Search::BAB::run
virtual bool run(void)
Run test.
Definition search.cpp:457
Test::Search::BranchTypes
Iterator for branching types.
Definition search.cpp:651
Test::Search::BranchTypes::htb
HowToBranch htb(void) const
Return current branching type.
Definition search.cpp:669
Test::Search::BranchTypes::BranchTypes
BranchTypes(void)
Initialize iterator.
Definition search.cpp:659
Test::Search::BranchTypes::operator++
void operator++(void)
Increment to next branching type.
Definition search.cpp:665
Test::Search::BranchTypes::operator()
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:661
Test::Search::ConstrainTypes
Iterator for constrain types.
Definition search.cpp:677
Test::Search::ConstrainTypes::htc
HowToConstrain htc(void) const
Return current constrain type.
Definition search.cpp:695
Test::Search::ConstrainTypes::operator++
void operator++(void)
Increment to next constrain type.
Definition search.cpp:691
Test::Search::ConstrainTypes::operator()
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:687
Test::Search::ConstrainTypes::ConstrainTypes
ConstrainTypes(void)
Initialize iterator.
Definition search.cpp:685
Test::Search::Create
Help class to create and register tests.
Definition search.cpp:705
Test::Search::Create::Create
Create(void)
Perform creation and registration.
Definition search.cpp:708
Test::Search::DFS::run
virtual bool run(void)
Run test.
Definition search.cpp:376
Test::Search::DFS::DFS
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:369
Test::Search::FailImmediate::best
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:121
Test::Search::FailImmediate::x
IntVarArray x
Variables used.
Definition search.cpp:98
Test::Search::FailImmediate::FailImmediate
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:100
Test::Search::FailImmediate::FailImmediate
FailImmediate(FailImmediate &s)
Constructor for cloning s.
Definition search.cpp:106
Test::Search::FailImmediate::copy
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:110
Test::Search::FailImmediate::name
static std::string name(void)
Return name.
Definition search.cpp:125
Test::Search::FailImmediate::solutions
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:117
Test::Search::FailImmediate::constrain
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:114
Test::Search::HasSolutions::solutions
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:245
Test::Search::HasSolutions::copy
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:208
Test::Search::HasSolutions::name
static std::string name(void)
Return name.
Definition search.cpp:285
Test::Search::HasSolutions::best
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:257
Test::Search::HasSolutions::constrain
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition search.cpp:212
Test::Search::HasSolutions::master
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
Definition search.cpp:289
Test::Search::HasSolutions::htb3
HowToBranch htb3
Definition search.cpp:171
Test::Search::HasSolutions::htc
HowToConstrain htc
How to constrain.
Definition search.cpp:173
Test::Search::HasSolutions::HasSolutions
HasSolutions(HasSolutions &s)
Constructor for cloning s.
Definition search.cpp:202
Test::Search::HasSolutions::x
IntVarArray x
Variables used.
Definition search.cpp:169
Test::Search::HasSolutions::htb1
HowToBranch htb1
How to branch.
Definition search.cpp:171
Test::Search::HasSolutions::HasSolutions
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition search.cpp:191
Test::Search::HasSolutions::branch
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition search.cpp:175
Test::Search::HasSolutions::htb2
HowToBranch htb2
Definition search.cpp:171
Test::Search::LDS::run
virtual bool run(void)
Run test.
Definition search.cpp:414
Test::Search::LDS::LDS
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Definition search.cpp:408
Test::Search::PBS::PBS
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
Definition search.cpp:531
Test::Search::PBS::run
virtual bool run(void)
Run test.
Definition search.cpp:535
Test::Search::RBS::RBS
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition search.cpp:491
Test::Search::RBS::run
virtual bool run(void)
Run test.
Definition search.cpp:495
Test::Search::SEBPBS
Test for portfolio-based search using SEBs
Definition search.cpp:577
Test::Search::SEBPBS::SEBPBS
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
Definition search.cpp:587
Test::Search::SEBPBS::run
virtual bool run(void)
Run test.
Definition search.cpp:591
Test::Search::SolveImmediate::solutions
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:152
Test::Search::SolveImmediate::x
IntVarArray x
Variables used.
Definition search.cpp:134
Test::Search::SolveImmediate::best
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:156
Test::Search::SolveImmediate::copy
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:144
Test::Search::SolveImmediate::name
static std::string name(void)
Return name.
Definition search.cpp:160
Test::Search::SolveImmediate::SolveImmediate
SolveImmediate(SolveImmediate &s)
Constructor for cloning s.
Definition search.cpp:140
Test::Search::SolveImmediate::SolveImmediate
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:136
Test::Search::SolveImmediate::constrain
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:148
Test::Search::TestSpace::solutions
virtual int solutions(void) const =0
Return number of solutions.
Test::Search::TestSpace::master
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
Definition search.cpp:83
Test::Search::TestSpace::TestSpace
TestSpace(void)
Constructor for space creation.
Definition search.cpp:75
Test::Search::TestSpace::TestSpace
TestSpace(TestSpace &s)
Constructor for cloning s.
Definition search.cpp:77
Test::Search::TestSpace::best
virtual bool best(void) const =0
Verify that this is best solution.
Test::Search::Test::str
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition search.cpp:319
Test::Search::Test::Test
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition search.cpp:350
Test::Search::Test::htc
HowToConstrain htc
How to constrain.
Definition search.cpp:317
Test::Search::Test::str
static std::string str(HowToBranch htb)
Map branching to string.
Definition search.cpp:325
Test::Search::Test::htb1
HowToBranch htb1
How to branch.
Definition search.cpp:315
Test::Search::Test::str
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition search.cpp:337
Test::Search::Test::htb3
HowToBranch htb3
Definition search.cpp:315
Test::Search::Test::htb2
HowToBranch htb2
Definition search.cpp:315
Gecode::Space::fail
void fail(void)
Fail space.
Definition core.hpp:4030
Gecode::assign
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
Gecode::branch
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
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
Gecode::IRT_GR
@ IRT_GR
Greater ( ).
Definition int.hh:931
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( ).
Definition int.hh:928
Gecode::BOT_AND
@ BOT_AND
Conjunction.
Definition int.hh:951
Gecode::Space::Space
Space(void)
Default constructor.
Definition core.cpp:115
Gecode::Space::constrain
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
Gecode::pbs
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:309
Gecode::bab
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
Gecode::lds
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
Gecode::rbs
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:111
minimodel.hh
Gecode::Int
Finite domain integers.
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
Gecode::lex
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
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::abs
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition arithmetic.cpp:41
Gecode::INT_VALUES_MIN
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition val.hpp:100
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Gecode::dfs
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
Gecode::INT_ASSIGN_MIN
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
Test::Search::HowToBranch
HowToBranch
Values for selecting branchers.
Definition search.cpp:48
Test::Search::HTB_BINARY
@ HTB_BINARY
Branch with two alternatives.
Definition search.cpp:51
Test::Search::HTB_NONE
@ HTB_NONE
Do not branch.
Definition search.cpp:49
Test::Search::HTB_UNARY
@ HTB_UNARY
Branch with single alternative.
Definition search.cpp:50
Test::Search::HTB_NARY
@ HTB_NARY
Branch with many alternatives.
Definition search.cpp:52
Test::Search::HowToConstrain
HowToConstrain
Values for selecting how to constrain.
Definition search.cpp:56
Test::Search::HTC_BAL_GR
@ HTC_BAL_GR
Constrain for largest balance.
Definition search.cpp:61
Test::Search::HTC_LEX_LE
@ HTC_LEX_LE
Constrain for lexically smallest.
Definition search.cpp:58
Test::Search::HTC_LEX_GR
@ HTC_LEX_GR
Constrain for lexically biggest.
Definition search.cpp:59
Test::Search::HTC_BAL_LE
@ HTC_BAL_LE
Constrain for smallest balance.
Definition search.cpp:60
Test::Search::HTC_NONE
@ HTC_NONE
Do not constrain.
Definition search.cpp:57
Test::Search::c
Create c
Definition search.cpp:794
Test::Search::WhichModel
WhichModel
Values for selecting models.
Definition search.cpp:65
Test::Search::WM_FAIL_SEARCH
@ WM_FAIL_SEARCH
Model without solutions.
Definition search.cpp:67
Test::Search::WM_SOLUTIONS
@ WM_SOLUTIONS
Model with solutions.
Definition search.cpp:68
Test::Search::WM_FAIL_IMMEDIATE
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
Definition search.cpp:66
Test
General test support.
Definition afc.cpp:39
search.hh
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
test.hh