81 virtual bool best(
void)
const = 0;
85 if (mi.
last() != NULL)
107 x.update(*
this, s.
x);
121 virtual bool best(
void)
const {
125 static std::string
name(
void) {
141 x.update(*
this, s.
x);
156 virtual bool best(
void)
const {
160 static std::string
name(
void) {
205 x.update(*
this, s.
x);
221 for (
int i=0; i<6; i++)
222 y[i] =
IntVar(*
this, s.
x[i].val(), s.
x[i].val());
230 for (
int i=0; i<6; i++)
231 y[i] =
IntVar(*
this, s.
x[i].val(), s.
x[i].val());
232 IntVar xs(*
this, -18, 18);
233 IntVar ys(*
this, -18, 18);
234 rel(*
this,
x[0]+
x[1]+
x[2]-
x[3]-
x[4]-
x[5] == xs);
235 rel(*
this,
y[0]+
y[1]+
y[2]-
y[3]-
y[4]-
y[5] == ys);
257 virtual bool best(
void)
const {
265 return ((
x[0].val()==4) && (
x[1].val()==5) &&
266 (
x[2].val()==2) && (
x[3].val()==3) &&
267 (
x[4].val()==0) && (
x[5].val()==1));
269 return ((
x[0].val()==5) && (
x[1].val()==4) &&
270 (
x[2].val()==3) && (
x[3].val()==2) &&
271 (
x[4].val()==1) && (
x[5].val()==0));
273 return ((
x[0].val()==4) && (
x[1].val()==5) &&
274 (
x[2].val()==2) && (
x[3].val()==3) &&
275 (
x[4].val()==0) && (
x[5].val()==1));
277 return ((
x[0].val()==4) && (
x[1].val()==5) &&
278 (
x[2].val()==3) && (
x[3].val()==2) &&
279 (
x[4].val()==0) && (
x[5].val()==1));
285 static std::string
name(
void) {
292 if (mi.
last() != NULL) {
296 for (
int i=0; i<
x.size(); i++)
297 b <<
expr(*
this,
x[i] == s->
x[i]);
319 static std::string
str(
unsigned int i) {
353 :
Base(
"Search::"+s),
358 template<
class Model>
370 unsigned int c_d0,
unsigned int a_d0,
unsigned int t0)
385 int n = m->solutions();
388 Model* s =
dfs.next();
392 if ((s == NULL) && !
dfs.stopped())
394 f.limit(f.limit()+2);
401 template<
class Model>
422 int n = m->solutions();
425 Model* s =
lds.next();
429 if ((s == NULL) && !
lds.stopped())
431 f.limit(f.limit()+2);
438 template<
class Model>
451 unsigned int c_d0,
unsigned int a_d0,
unsigned int t0)
469 Model* s =
bab.next();
473 if ((s == NULL) && !
bab.stopped())
475 f.limit(f.limit()+2);
477 bool ok = (b == NULL) || b->best();
484 template<
class Model,
template<
class>
class Engine>
491 RBS(
const std::string& e,
unsigned int t0)
504 int n = m->solutions();
507 Model* s =
rbs.next();
511 if ((s == NULL) && !
rbs.stopped())
513 f.limit(f.limit()+2);
520 template<
class Model,
template<
class>
class Engine>
531 PBS(
const std::string& e,
bool b,
unsigned int a0,
unsigned int t0)
547 Model* s =
pbs.next();
551 if ((s == NULL) && !
pbs.stopped())
553 f.limit(f.limit()+2);
555 bool ok = (b == NULL) || b->best();
559 int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
562 Model* s =
pbs.next();
566 if ((s == NULL) && !
pbs.stopped())
568 f.limit(f.limit()+2);
576 template<
class Model>
587 SEBPBS(
const std::string& e,
bool b,
unsigned int mt0,
unsigned int st0)
588 :
Test(
"PBS::SEB::"+e+
"::"+Model::
name()+
"::"+
str(mt0)+
"::"+
str(st0),
615 Model* s =
pbs.next();
619 if ((s == NULL) && !
pbs.stopped())
621 f.limit(f.limit()+2);
623 bool ok = (b == NULL) || b->best();
633 int n = 3 * m->solutions();
637 Model* s =
pbs.next();
641 if ((s == NULL) && !
pbs.stopped())
643 f.limit(f.limit()+2);
674 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
700 const HowToConstrain ConstrainTypes::htcs[4] =
701 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
710 for (
unsigned int t = 1; t<=4; t++)
711 for (
unsigned int c_d = 1; c_d<10; c_d++)
712 for (
unsigned int a_d = 1; a_d<=c_d; a_d++) {
717 (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
727 for (
unsigned int t = 1; t<=4; t++) {
738 for (
unsigned int t = 1; t<=4; t++)
739 for (
unsigned int c_d = 1; c_d<10; c_d++)
740 for (
unsigned int a_d = 1; a_d<=c_d; a_d++) {
746 (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
757 for (
unsigned int t=1; t<=4; t++) {
769 for (
unsigned int a=1; a<=4; a++)
770 for (
unsigned int t=1; t<=2*a; t++) {
782 for (
unsigned int mt=1; mt<=3; mt += 2)
783 for (
unsigned int st=1; st<=8; st++) {
Depth-first branch-and-bound search engine.
Passing Boolean variables.
Depth-first search engine.
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.
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Stop-object based on number of failures
unsigned int c_d
Create a clone after every c_d commits (commit distance)
unsigned int d_l
Discrepancy limit (for LDS)
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 int assets
Number of assets (engines) in a portfolio.
double threads
Number of threads to use.
Base(const std::string &s)
Create and register test with name s.
const std::string & name(void) const
Return name of test.
BAB(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.
Help class to create and register tests.
Create(void)
Perform creation and registration.
virtual bool run(void)
Run test.
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
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.
virtual bool run(void)
Run test.
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
virtual bool run(void)
Run test.
RBS(const std::string &e, unsigned int t0)
Initialize test.
virtual bool run(void)
Run test.
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 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.
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.
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
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
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 .
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Post propagator for SetVar SetOpType SetVar y
IntValBranch INT_VAL_MIN(void)
Select smallest value.
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.
HowToBranch
Values for selecting branchers.
@ HTB_BINARY
Branch with two alternatives.
@ HTB_UNARY
Branch with single alternative.
@ HTB_NARY
Branch with many alternatives.
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.
WhichModel
Values for selecting models.
@ WM_FAIL_SEARCH
Model without solutions.
@ WM_SOLUTIONS
Model with solutions.
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
#define GECODE_NEVER
Assert that this command is never executed.