Generated on Sat Feb 7 2015 02:01:32 for Gecode by doxygen 1.8.9.1
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: 2014-10-21 17:09:50 +0200 (Tue, 21 Oct 2014) $ by $Author: schulte $
11  * $Revision: 14258 $
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;
87  virtual bool master(const CRI& cri) {
88  if (cri.last() != NULL)
89  constrain(*cri.last());
90  return false;
91  }
92  };
93 
95  class FailImmediate : public TestSpace {
96  public:
102  : x(*this,1,0,0) {
103  rel(*this, x[0], IRT_EQ, 1);
104  }
106  FailImmediate(bool share, FailImmediate& s) : TestSpace(share,s) {
107  x.update(*this, share, s.x);
108  }
110  virtual Space* copy(bool share) {
111  return new FailImmediate(share,*this);
112  }
114  virtual void constrain(const Space&) {
115  }
117  virtual int solutions(void) const {
118  return 0;
119  }
121  virtual bool best(void) const {
122  return false;
123  }
125  static std::string name(void) {
126  return "Fail";
127  }
128  };
129 
131  class SolveImmediate : public TestSpace {
132  public:
138  : x(*this,1,0,0) {}
140  SolveImmediate(bool share, SolveImmediate& s) : TestSpace(share,s) {
141  x.update(*this, share, s.x);
142  }
144  virtual Space* copy(bool share) {
145  return new SolveImmediate(share,*this);
146  }
148  virtual void constrain(const Space&) {
149  fail();
150  }
152  virtual int solutions(void) const {
153  return 1;
154  }
156  virtual bool best(void) const {
157  return true;
158  }
160  static std::string name(void) {
161  return "Solve";
162  }
163  };
164 
166  class HasSolutions : public TestSpace {
167  public:
171  HowToBranch htb1, htb2, htb3;
175  void branch(const IntVarArgs& x, HowToBranch htb) {
176  switch (htb) {
177  case HTB_NONE:
178  break;
179  case HTB_UNARY:
180  assign(*this, x, INT_ASSIGN_MIN());
181  break;
182  case HTB_BINARY:
183  Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
184  break;
185  case HTB_NARY:
187  break;
188  }
189  }
193  : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
194  distinct(*this, x);
195  rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
196  rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
197  IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
198  IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
199  IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
200  }
202  HasSolutions(bool share, HasSolutions& s)
203  : TestSpace(share,s),
204  htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
205  x.update(*this, share, s.x);
206  }
208  virtual Space* copy(bool share) {
209  return new HasSolutions(share,*this);
210  }
212  virtual void constrain(const Space& _s) {
213  const HasSolutions& s = static_cast<const HasSolutions&>(_s);
214  switch (htc) {
215  case HTC_NONE:
216  break;
217  case HTC_LEX_LE:
218  case HTC_LEX_GR:
219  {
220  IntVarArgs y(6);
221  for (int i=0; i<6; i++)
222  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
223  lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
224  break;
225  }
226  case HTC_BAL_LE:
227  case HTC_BAL_GR:
228  {
229  IntVarArgs y(6);
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);
236  rel(*this,
237  expr(*this,abs(xs)),
238  (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
239  expr(*this,abs(ys)));
240  break;
241  }
242  }
243  }
245  virtual int solutions(void) const {
246  if (htb1 == HTB_NONE) {
247  assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
248  return 1;
249  }
250  if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
251  return 0;
252  if (htb3 == HTB_UNARY)
253  return 4;
254  return 8;
255  }
257  virtual bool best(void) const {
258  if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
259  (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
260  return true;
261  switch (htc) {
262  case HTC_NONE:
263  return true;
264  case HTC_LEX_LE:
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));
268  case HTC_LEX_GR:
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));
272  case HTC_BAL_LE:
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));
276  case HTC_BAL_GR:
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));
280  default: GECODE_NEVER;
281  }
282  return false;
283  }
285  static std::string name(void) {
286  return "Sol";
287  }
289  virtual void master(unsigned long int i, const Space* _s,
290  NoGoods&) {
291  const HasSolutions* s = static_cast<const HasSolutions*>(_s);
292  if (s != NULL) {
293  BoolVarArgs b;
294  for (int i=0; i<x.size(); i++)
295  b << expr(*this, x[i] == s->x[i]);
296  rel(*this, BOT_AND, b, 0);
297  }
298  }
299  };
300 
302  class Test : public Base {
303  public:
305  HowToBranch htb1, htb2, htb3;
309  static std::string str(unsigned int i) {
310  std::stringstream s;
311  s << i;
312  return s.str();
313  }
315  static std::string str(HowToBranch htb) {
316  switch (htb) {
317  case HTB_NONE: return "None";
318  case HTB_UNARY: return "Unary";
319  case HTB_BINARY: return "Binary";
320  case HTB_NARY: return "Nary";
321  default: GECODE_NEVER;
322  }
323  GECODE_NEVER;
324  return "";
325  }
327  static std::string str(HowToConstrain htc) {
328  switch (htc) {
329  case HTC_NONE: return "None";
330  case HTC_LEX_LE: return "LexLe";
331  case HTC_LEX_GR: return "LexGr";
332  case HTC_BAL_LE: return "BalLe";
333  case HTC_BAL_GR: return "BalGr";
334  default: GECODE_NEVER;
335  }
336  GECODE_NEVER;
337  return "";
338  }
340  Test(const std::string& s,
341  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
343  : Base("Search::"+s),
344  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
345  };
346 
348  template<class Model>
349  class DFS : public Test {
350  private:
352  unsigned int c_d;
354  unsigned int a_d;
356  unsigned int t;
357  public:
360  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
361  : Test("DFS::"+Model::name()+"::"+
362  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
363  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
364  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
366  virtual bool run(void) {
367  Model* m = new Model(htb1,htb2,htb3);
370  o.c_d = c_d;
371  o.a_d = a_d;
372  o.threads = t;
373  o.stop = &f;
374  Gecode::DFS<Model> dfs(m,o);
375  int n = m->solutions();
376  delete m;
377  while (true) {
378  Model* s = dfs.next();
379  if (s != NULL) {
380  n--; delete s;
381  }
382  if ((s == NULL) && !dfs.stopped())
383  break;
384  f.limit(f.limit()+2);
385  }
386  return n == 0;
387  }
388  };
389 
391  template<class Model>
392  class BAB : public Test {
393  private:
395  unsigned int c_d;
397  unsigned int a_d;
399  unsigned int t;
400  public:
403  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
404  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
405  : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
406  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
407  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
408  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
410  virtual bool run(void) {
411  Model* m = new Model(htb1,htb2,htb3,htc);
414  o.c_d = c_d;
415  o.a_d = a_d;
416  o.threads = t;
417  o.stop = &f;
418  Gecode::BAB<Model> bab(m,o);
419  delete m;
420  Model* b = NULL;
421  while (true) {
422  Model* s = bab.next();
423  if (s != NULL) {
424  delete b; b=s;
425  }
426  if ((s == NULL) && !bab.stopped())
427  break;
428  f.limit(f.limit()+2);
429  }
430  bool ok = (b == NULL) || b->best();
431  delete b;
432  return ok;
433  }
434  };
435 
437  template<class Model, template<class> class Engine>
438  class RBS : public Test {
439  private:
441  unsigned int t;
442  public:
444  RBS(const std::string& e, unsigned int t0)
445  : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
446  HTB_BINARY,HTB_BINARY,HTB_BINARY), t(t0) {}
448  virtual bool run(void) {
449  Model* m = new Model(htb1,htb2,htb3);
452  o.threads = t;
453  o.stop = &f;
456  int n = m->solutions();
457  delete m;
458  while (true) {
459  Model* s = rbs.next();
460  if (s != NULL) {
461  n--; delete s;
462  }
463  if ((s == NULL) && !rbs.stopped())
464  break;
465  f.limit(f.limit()+2);
466  }
467  return n == 0;
468  }
469  };
470 
472  class BranchTypes {
473  private:
475  static const HowToBranch htbs[3];
477  int i;
478  public:
480  BranchTypes(void) : i(0) {}
482  bool operator()(void) const {
483  return i<3;
484  }
486  void operator++(void) {
487  i++;
488  }
490  HowToBranch htb(void) const {
491  return htbs[i];
492  }
493  };
494 
495  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
496 
499  private:
501  static const HowToConstrain htcs[4];
503  int i;
504  public:
506  ConstrainTypes(void) : i(0) {}
508  bool operator()(void) const {
509  return i<4;
510  }
512  void operator++(void) {
513  i++;
514  }
516  HowToConstrain htc(void) const {
517  return htcs[i];
518  }
519  };
520 
521  const HowToConstrain ConstrainTypes::htcs[4] =
523 
524 
526  class Create {
527  public:
529  Create(void) {
530  // Depth-first search
531  for (unsigned int t = 1; t<=4; t++)
532  for (unsigned int c_d = 1; c_d<10; c_d++)
533  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
534  for (BranchTypes htb1; htb1(); ++htb1)
535  for (BranchTypes htb2; htb2(); ++htb2)
536  for (BranchTypes htb3; htb3(); ++htb3)
537  (void) new DFS<HasSolutions>
538  (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
540  c_d, a_d, t);
542  c_d, a_d, t);
544  c_d, a_d, t);
545  }
546 
547  // Best solution search
548  for (unsigned int t = 1; t<=4; t++)
549  for (unsigned int c_d = 1; c_d<10; c_d++)
550  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
551  for (ConstrainTypes htc; htc(); ++htc)
552  for (BranchTypes htb1; htb1(); ++htb1)
553  for (BranchTypes htb2; htb2(); ++htb2)
554  for (BranchTypes htb3; htb3(); ++htb3) {
555  (void) new BAB<HasSolutions>
556  (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
557  c_d,a_d,t);
558  }
559  (void) new BAB<FailImmediate>
561  (void) new BAB<SolveImmediate>
563  (void) new BAB<HasSolutions>
565  }
566  // Restart-based search
567  for (unsigned int t = 1; t<=4; t++) {
568  (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
569  (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
570  (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
571  (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
572  (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
573  (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
574  }
575  }
576  };
577 
579  }
580 
581 }
582 
583 // 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:95
Model with solutions.
Definition: search.cpp:72
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:136
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:245
Iterator for branching types.
Definition: search.cpp:472
IntVarArray x
Variables used.
Definition: search.cpp:98
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:285
FailImmediate(bool share, FailImmediate &s)
Constructor for cloning s.
Definition: search.cpp:106
TestSpace(bool share, TestSpace &s)
Constructor for cloning s.
Definition: search.cpp:81
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:110
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:230
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:327
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:402
HasSolutions(bool share, HasSolutions &s)
Constructor for cloning s.
Definition: search.cpp:202
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
Less or equal ( )
Definition: int.hh:906
Conjunction.
Definition: int.hh:917
HowToConstrain htc
How to constrain.
Definition: search.cpp:307
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:148
Integer variable array.
Definition: int.hh:741
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition: search.cpp:359
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:144
void operator++(void)
Increment to next branching type.
Definition: search.cpp:486
Greater ( )
Definition: int.hh:909
HowToConstrain htc
How to constrain.
Definition: search.cpp:173
Current restart information during search.
Definition: core.hpp:1265
Computation spaces.
Definition: core.hpp:1362
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition: search.cpp:175
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:289
Create c
Definition: search.cpp:578
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:152
static std::string name(void)
Return name.
Definition: search.cpp:125
Create(void)
Perform creation and registration.
Definition: search.cpp:529
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:208
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition: search.cpp:340
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)
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:2721
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:121
virtual bool run(void)
Run test.
Definition: search.cpp:448
static std::string str(HowToBranch htb)
Map branching to string.
Definition: search.cpp:315
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:508
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:530
Model without solutions.
Definition: search.cpp:71
Space that immediately fails.
Definition: search.cpp:95
unsigned long int limit(void) const
Return current limit.
Definition: stop.hpp:88
void operator++(void)
Increment to next constrain type.
Definition: search.cpp:512
HowToBranch htb(void) const
Return current branching type.
Definition: search.cpp:490
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition: search.cpp:309
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:516
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:100
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
HowToBranch htb3
Definition: search.cpp:305
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:160
Less ( )
Definition: int.hh:907
virtual bool master(const CRI &cri)
Master configuration function that does not restart.
Definition: search.cpp:87
Space that is immediately solved.
Definition: search.cpp:131
Branch with many alternatives.
Definition: search.cpp:56
Passing integer variables.
Definition: int.hh:636
Passing Boolean variables.
Definition: int.hh:690
Space that requires propagation and has solutions.
Definition: search.cpp:166
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:83
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
General test support.
Definition: afc.cpp:43
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:498
BrancherHandle assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
Constrain for smallest balance.
Definition: search.cpp:64
Help class to create and register tests.
Definition: search.cpp:526
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:482
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:191
ConstrainTypes(void)
Initialize iterator.
Definition: search.cpp:506
IntVarArray x
Variables used.
Definition: search.cpp:169
Integer variables.
Definition: int.hh:350
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:410
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:156
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:480
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:212
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:117
virtual bool run(void)
Run test.
Definition: search.cpp:366
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Finite domain integers.
Definition: abs.hpp:42
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:140
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:114
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition: search.cpp:444
#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:494
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:257
IntVarArray x
Variables used.
Definition: search.cpp:134