Generated on Sat Sep 13 2014 13:24:52 for Gecode by doxygen 1.8.7
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.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2008
8  *
9  * Last modified:
10  * $Date: 2013-07-15 12:02:18 +0200 (Mon, 15 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13880 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
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>
40 
41 #include "test/test.hh"
42 
43 namespace Test {
44 
46  namespace Search {
47 
48  using namespace Gecode;
49  using namespace Gecode::Int;
50 
52  enum HowToBranch {
57  };
58 
66  };
67 
69  enum WhichModel {
73  };
74 
76  class TestSpace : public Space {
77  public:
79  TestSpace(void) {}
81  TestSpace(bool share, TestSpace& s) : Space(share,s) {}
83  virtual int solutions(void) const = 0;
85  virtual bool best(void) const = 0;
86  };
87 
89  class FailImmediate : public TestSpace {
90  public:
96  : x(*this,1,0,0) {
97  rel(*this, x[0], IRT_EQ, 1);
98  }
100  FailImmediate(bool share, FailImmediate& s) : TestSpace(share,s) {
101  x.update(*this, share, s.x);
102  }
104  virtual Space* copy(bool share) {
105  return new FailImmediate(share,*this);
106  }
108  virtual void constrain(const Space&) {
109  }
111  virtual int solutions(void) const {
112  return 0;
113  }
115  virtual bool best(void) const {
116  return false;
117  }
119  static std::string name(void) {
120  return "Fail";
121  }
122  };
123 
125  class SolveImmediate : public TestSpace {
126  public:
132  : x(*this,1,0,0) {}
134  SolveImmediate(bool share, SolveImmediate& s) : TestSpace(share,s) {
135  x.update(*this, share, s.x);
136  }
138  virtual Space* copy(bool share) {
139  return new SolveImmediate(share,*this);
140  }
142  virtual void constrain(const Space&) {
143  fail();
144  }
146  virtual int solutions(void) const {
147  return 1;
148  }
150  virtual bool best(void) const {
151  return true;
152  }
154  static std::string name(void) {
155  return "Solve";
156  }
157  };
158 
160  class HasSolutions : public TestSpace {
161  public:
165  HowToBranch htb1, htb2, htb3;
169  void branch(const IntVarArgs& x, HowToBranch htb) {
170  switch (htb) {
171  case HTB_NONE:
172  break;
173  case HTB_UNARY:
174  assign(*this, x, INT_ASSIGN_MIN());
175  break;
176  case HTB_BINARY:
177  Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
178  break;
179  case HTB_NARY:
181  break;
182  }
183  }
187  : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
188  distinct(*this, x);
189  rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
190  rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
191  IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
192  IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
193  IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
194  }
196  HasSolutions(bool share, HasSolutions& s)
197  : TestSpace(share,s),
198  htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
199  x.update(*this, share, s.x);
200  }
202  virtual Space* copy(bool share) {
203  return new HasSolutions(share,*this);
204  }
206  virtual void constrain(const Space& _s) {
207  const HasSolutions& s = static_cast<const HasSolutions&>(_s);
208  switch (htc) {
209  case HTC_NONE:
210  break;
211  case HTC_LEX_LE:
212  case HTC_LEX_GR:
213  {
214  IntVarArgs y(6);
215  for (int i=0; i<6; i++)
216  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
217  lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
218  break;
219  }
220  case HTC_BAL_LE:
221  case HTC_BAL_GR:
222  {
223  IntVarArgs y(6);
224  for (int i=0; i<6; i++)
225  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
226  IntVar xs(*this, -18, 18);
227  IntVar ys(*this, -18, 18);
228  rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
229  rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
230  rel(*this,
231  expr(*this,abs(xs)),
232  (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
233  expr(*this,abs(ys)));
234  break;
235  }
236  }
237  }
239  virtual int solutions(void) const {
240  if (htb1 == HTB_NONE) {
241  assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
242  return 1;
243  }
244  if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
245  return 0;
246  if (htb3 == HTB_UNARY)
247  return 4;
248  return 8;
249  }
251  virtual bool best(void) const {
252  if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
253  (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
254  return true;
255  switch (htc) {
256  case HTC_NONE:
257  return true;
258  case HTC_LEX_LE:
259  return ((x[0].val()==4) && (x[1].val()==5) &&
260  (x[2].val()==2) && (x[3].val()==3) &&
261  (x[4].val()==0) && (x[5].val()==1));
262  case HTC_LEX_GR:
263  return ((x[0].val()==5) && (x[1].val()==4) &&
264  (x[2].val()==3) && (x[3].val()==2) &&
265  (x[4].val()==1) && (x[5].val()==0));
266  case HTC_BAL_LE:
267  return ((x[0].val()==4) && (x[1].val()==5) &&
268  (x[2].val()==2) && (x[3].val()==3) &&
269  (x[4].val()==0) && (x[5].val()==1));
270  case HTC_BAL_GR:
271  return ((x[0].val()==4) && (x[1].val()==5) &&
272  (x[2].val()==3) && (x[3].val()==2) &&
273  (x[4].val()==0) && (x[5].val()==1));
274  default: GECODE_NEVER;
275  }
276  return false;
277  }
279  static std::string name(void) {
280  return "Sol";
281  }
283  virtual void master(unsigned long int i, const Space* _s,
284  NoGoods&) {
285  const HasSolutions* s = static_cast<const HasSolutions*>(_s);
286  if (s != NULL) {
287  BoolVarArgs b;
288  for (int i=0; i<x.size(); i++)
289  b << expr(*this, x[i] == s->x[i]);
290  rel(*this, BOT_AND, b, 0);
291  }
292  }
293  };
294 
296  class Test : public Base {
297  public:
299  HowToBranch htb1, htb2, htb3;
303  static std::string str(unsigned int i) {
304  std::stringstream s;
305  s << i;
306  return s.str();
307  }
309  static std::string str(HowToBranch htb) {
310  switch (htb) {
311  case HTB_NONE: return "None";
312  case HTB_UNARY: return "Unary";
313  case HTB_BINARY: return "Binary";
314  case HTB_NARY: return "Nary";
315  default: GECODE_NEVER;
316  }
317  GECODE_NEVER;
318  return "";
319  }
321  static std::string str(HowToConstrain htc) {
322  switch (htc) {
323  case HTC_NONE: return "None";
324  case HTC_LEX_LE: return "LexLe";
325  case HTC_LEX_GR: return "LexGr";
326  case HTC_BAL_LE: return "BalLe";
327  case HTC_BAL_GR: return "BalGr";
328  default: GECODE_NEVER;
329  }
330  GECODE_NEVER;
331  return "";
332  }
334  Test(const std::string& s,
335  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
337  : Base("Search::"+s),
338  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
339  };
340 
342  template<class Model>
343  class DFS : public Test {
344  private:
346  unsigned int c_d;
348  unsigned int a_d;
350  unsigned int t;
351  public:
354  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
355  : Test("DFS::"+Model::name()+"::"+
356  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
357  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
358  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
360  virtual bool run(void) {
361  Model* m = new Model(htb1,htb2,htb3);
364  o.c_d = c_d;
365  o.a_d = a_d;
366  o.threads = t;
367  o.stop = &f;
368  Gecode::DFS<Model> dfs(m,o);
369  int n = m->solutions();
370  delete m;
371  while (true) {
372  Model* s = dfs.next();
373  if (s != NULL) {
374  n--; delete s;
375  }
376  if ((s == NULL) && !dfs.stopped())
377  break;
378  f.limit(f.limit()+2);
379  }
380  return n == 0;
381  }
382  };
383 
385  template<class Model>
386  class BAB : public Test {
387  private:
389  unsigned int c_d;
391  unsigned int a_d;
393  unsigned int t;
394  public:
397  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
398  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
399  : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
400  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
401  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
402  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
404  virtual bool run(void) {
405  Model* m = new Model(htb1,htb2,htb3,htc);
408  o.c_d = c_d;
409  o.a_d = a_d;
410  o.threads = t;
411  o.stop = &f;
412  Gecode::BAB<Model> bab(m,o);
413  delete m;
414  Model* b = NULL;
415  while (true) {
416  Model* s = bab.next();
417  if (s != NULL) {
418  delete b; b=s;
419  }
420  if ((s == NULL) && !bab.stopped())
421  break;
422  f.limit(f.limit()+2);
423  }
424  bool ok = (b == NULL) || b->best();
425  delete b;
426  return ok;
427  }
428  };
429 
431  template<class Model, template<class> class Engine>
432  class RBS : public Test {
433  private:
435  unsigned int t;
436  public:
438  RBS(const std::string& e, unsigned int t0)
439  : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
442  virtual bool run(void) {
443  Model* m = new Model(htb1,htb2,htb3);
446  o.threads = t;
447  o.stop = &f;
450  int n = m->solutions();
451  delete m;
452  while (true) {
453  Model* s = rbs.next();
454  if (s != NULL) {
455  n--; delete s;
456  }
457  if ((s == NULL) && !rbs.stopped())
458  break;
459  f.limit(f.limit()+2);
460  }
461  return n == 0;
462  }
463  };
464 
466  class BranchTypes {
467  private:
469  static const HowToBranch htbs[3];
471  int i;
472  public:
474  BranchTypes(void) : i(0) {}
476  bool operator()(void) const {
477  return i<3;
478  }
480  void operator++(void) {
481  i++;
482  }
484  HowToBranch htb(void) const {
485  return htbs[i];
486  }
487  };
488 
489  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
490 
493  private:
495  static const HowToConstrain htcs[4];
497  int i;
498  public:
500  ConstrainTypes(void) : i(0) {}
502  bool operator()(void) const {
503  return i<4;
504  }
506  void operator++(void) {
507  i++;
508  }
510  HowToConstrain htc(void) const {
511  return htcs[i];
512  }
513  };
514 
515  const HowToConstrain ConstrainTypes::htcs[4] =
517 
518 
520  class Create {
521  public:
523  Create(void) {
524  // Depth-first search
525  for (unsigned int t = 1; t<=4; t++)
526  for (unsigned int c_d = 1; c_d<10; c_d++)
527  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
528  for (BranchTypes htb1; htb1(); ++htb1)
529  for (BranchTypes htb2; htb2(); ++htb2)
530  for (BranchTypes htb3; htb3(); ++htb3)
531  (void) new DFS<HasSolutions>
532  (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
534  c_d, a_d, t);
536  c_d, a_d, t);
538  c_d, a_d, t);
539  }
540 
541  // Best solution search
542  for (unsigned int t = 1; t<=4; t++)
543  for (unsigned int c_d = 1; c_d<10; c_d++)
544  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
545  for (ConstrainTypes htc; htc(); ++htc)
546  for (BranchTypes htb1; htb1(); ++htb1)
547  for (BranchTypes htb2; htb2(); ++htb2)
548  for (BranchTypes htb3; htb3(); ++htb3) {
549  (void) new BAB<HasSolutions>
550  (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
551  c_d,a_d,t);
552  }
553  (void) new BAB<FailImmediate>
555  (void) new BAB<SolveImmediate>
557  (void) new BAB<HasSolutions>
559  }
560  // Restart-based search
561  for (unsigned int t = 1; t<=4; t++) {
562  (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
563  (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
564  (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
565  (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
566  (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
567  (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
568  }
569  }
570  };
571 
573  }
574 
575 }
576 
577 // STATISTICS: test-search
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:213
bool stopped(void) const
Check whether engine has been stopped.
Definition: rbs.hpp:91
Model with solutions.
Definition: search.cpp:72
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:130
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:239
Iterator for branching types.
Definition: search.cpp:466
IntVarArray x
Variables used.
Definition: search.cpp:92
NodeType t
Type of node.
Definition: bool-expr.cpp:234
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
static std::string name(void)
Return name.
Definition: search.cpp:279
FailImmediate(bool share, FailImmediate &s)
Constructor for cloning s.
Definition: search.cpp:100
TestSpace(bool share, TestSpace &s)
Constructor for cloning s.
Definition: search.cpp:81
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:104
Meta-engine performing restart-based search.
Definition: search.hh:236
static Cutoff * geometric(unsigned long int scale=1U, double base=1.5)
Definition: cutoff.cpp:177
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:211
Search engine options
Definition: search.hh:204
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition: search.cpp:321
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:396
HasSolutions(bool share, HasSolutions &s)
Constructor for cloning s.
Definition: search.cpp:196
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
Less or equal ( )
Definition: int.hh:904
Conjunction.
Definition: int.hh:915
HowToConstrain htc
How to constrain.
Definition: search.cpp:301
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:142
Integer variable array.
Definition: int.hh:739
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition: search.cpp:353
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:138
void operator++(void)
Increment to next branching type.
Definition: search.cpp:480
Greater ( )
Definition: int.hh:907
HowToConstrain htc
How to constrain.
Definition: search.cpp:167
Base class for search tests
Definition: search.cpp:296
Computation spaces.
Definition: core.hpp:1325
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition: search.cpp:169
virtual void master(unsigned long int i, const Space *_s, NoGoods &)
Rule out that solution is found more than once during restarts.
Definition: search.cpp:283
Create c
Definition: search.cpp:572
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:146
static std::string name(void)
Return name.
Definition: search.cpp:119
Create(void)
Perform creation and registration.
Definition: search.cpp:523
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:202
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition: search.cpp:334
Model that fails immediately.
Definition: search.cpp:70
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:219
double threads
Number of threads to use.
Definition: search.hh:209
Constrain for lexically smallest.
Definition: search.cpp:62
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:902
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:115
virtual bool run(void)
Run test.
Definition: search.cpp:442
static std::string str(HowToBranch htb)
Map branching to string.
Definition: search.cpp:309
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:502
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:207
Depth-first branch-and-bound search engine.
Definition: search.hh:525
Model without solutions.
Definition: search.cpp:71
Space that immediately fails.
Definition: search.cpp:89
unsigned long int limit(void) const
Return current limit.
Definition: stop.hpp:88
void operator++(void)
Increment to next constrain type.
Definition: search.cpp:506
HowToBranch htb(void) const
Return current branching type.
Definition: search.cpp:484
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition: search.cpp:303
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
HowToConstrain htc(void) const
Return current constrain type.
Definition: search.cpp:510
WhichModel
Values for selecting models.
Definition: search.cpp:69
Branch with two alternatives.
Definition: search.cpp:55
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntConLevel icl=ICL_DEF)
Post lexical order between x and y.
Definition: minimodel.hh:1855
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:94
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
HowToBranch htb3
Definition: search.cpp:299
TestSpace(void)
Constructor for space creation.
Definition: search.cpp:79
Base class for all tests to be run
Definition: test.hh:107
static std::string name(void)
Return name.
Definition: search.cpp:154
Less ( )
Definition: int.hh:905
Space that is immediately solved.
Definition: search.cpp:125
struct Gecode::@512::NNF::@54::@55 b
For binary nodes (and, or, eqv)
Branch with many alternatives.
Definition: search.cpp:56
Passing integer variables.
Definition: int.hh:634
Passing Boolean variables.
Definition: int.hh:688
Space that requires propagation and has solutions.
Definition: search.cpp:160
Branch with single alternative.
Definition: search.cpp:54
T * next(void)
Return next solution (NULL, if non exists or search has been stopped)
Definition: rbs.hpp:79
bool stopped(void) const
Check whether engine has been stopped.
Definition: dfs.hpp:64
bool stopped(void) const
Check whether engine has been stopped.
Definition: bab.hpp:68
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:120
Iterator for constrain types.
Definition: search.cpp:492
BrancherHandle assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Constrain for smallest balance.
Definition: search.cpp:64
Help class to create and register tests.
Definition: search.cpp:520
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:476
HowToConstrain
Values for selecting how to constrain.
Definition: search.cpp:60
No-goods recorded from restarts.
Definition: core.hpp:1240
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:185
ConstrainTypes(void)
Initialize iterator.
Definition: search.cpp:500
IntVarArray x
Variables used.
Definition: search.cpp:163
Integer variables.
Definition: int.hh:348
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
HowToBranch
Values for selecting branchers.
Definition: search.cpp:52
Constrain for lexically biggest.
Definition: search.cpp:63
virtual bool run(void)
Run test.
Definition: search.cpp:404
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:212
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:150
Space with information.
Definition: search.cpp:76
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:97
BranchTypes(void)
Initialize iterator.
Definition: search.cpp:474
Do not constrain.
Definition: search.cpp:61
Stop * stop
Stop object for stopping search.
Definition: search.hh:217
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition: search.cpp:206
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:111
virtual bool run(void)
Run test.
Definition: search.cpp:360
Constrain for largest balance.
Definition: search.cpp:65
BrancherHandle branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
Do not branch.
Definition: search.cpp:53
T * next(void)
Return next better solution (NULL, if none exists or search has been stopped)
Definition: bab.hpp:56
SolveImmediate(bool share, SolveImmediate &s)
Constructor for cloning s.
Definition: search.cpp:134
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:108
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition: search.cpp:438
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Engine * rbs(Space *s, MetaStop *stop, Engine *e, const Options &o)
Definition: rbs.cpp:44
Depth-first search engine.
Definition: search.hh:489
Stop-object based on number of failures
Definition: search.hh:307
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:379
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:251
IntVarArray x
Variables used.
Definition: search.cpp:128