Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/minimodel.hh>
35 #include <gecode/search.hh>
36 
37 #include "test/test.hh"
38 
39 namespace Test {
40 
42  namespace Search {
43 
44  using namespace Gecode;
45  using namespace Gecode::Int;
46 
48  enum HowToBranch {
52  HTB_NARY
53  };
54 
61  HTC_BAL_GR
62  };
63 
65  enum WhichModel {
69  };
70 
72  class TestSpace : public Space {
73  public:
75  TestSpace(void) {}
79  virtual int solutions(void) const = 0;
81  virtual bool best(void) const = 0;
83  virtual bool master(const MetaInfo& mi) {
84  if (mi.type() == MetaInfo::RESTART) {
85  if (mi.last() != NULL)
86  constrain(*mi.last());
87  return false;
88  } else {
89  return false;
90  }
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  }
107  x.update(*this, s.x);
108  }
110  virtual Space* copy(void) {
111  return new FailImmediate(*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) {}
141  x.update(*this, s.x);
142  }
144  virtual Space* copy(void) {
145  return new SolveImmediate(*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:
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  }
203  : TestSpace(s),
204  htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
205  x.update(*this, s.x);
206  }
208  virtual Space* copy(void) {
209  return new HasSolutions(*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 bool master(const MetaInfo& mi) {
290  switch (mi.type()) {
291  case MetaInfo::RESTART:
292  if (mi.last() != NULL) {
293  const HasSolutions* s
294  = static_cast<const HasSolutions*>(mi.last());
295  BoolVarArgs b;
296  for (int i=0; i<x.size(); i++)
297  b << expr(*this, x[i] == s->x[i]);
298  rel(*this, BOT_AND, b, 0);
299  }
300  break;
301  case MetaInfo::PORTFOLIO:
302  // Do not kill the brancher!
303  break;
304  default:
305  break;
306  }
307  return false;
308  }
309  };
310 
312  class Test : public Base {
313  public:
315  HowToBranch htb1, htb2, htb3;
319  static std::string str(unsigned int i) {
320  std::stringstream s;
321  s << i;
322  return s.str();
323  }
325  static std::string str(HowToBranch htb) {
326  switch (htb) {
327  case HTB_NONE: return "None";
328  case HTB_UNARY: return "Unary";
329  case HTB_BINARY: return "Binary";
330  case HTB_NARY: return "Nary";
331  default: GECODE_NEVER;
332  }
333  GECODE_NEVER;
334  return "";
335  }
337  static std::string str(HowToConstrain htc) {
338  switch (htc) {
339  case HTC_NONE: return "None";
340  case HTC_LEX_LE: return "LexLe";
341  case HTC_LEX_GR: return "LexGr";
342  case HTC_BAL_LE: return "BalLe";
343  case HTC_BAL_GR: return "BalGr";
344  default: GECODE_NEVER;
345  }
346  GECODE_NEVER;
347  return "";
348  }
350  Test(const std::string& s,
351  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
353  : Base("Search::"+s),
354  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
355  };
356 
358  template<class Model>
359  class DFS : public Test {
360  private:
362  unsigned int c_d;
364  unsigned int a_d;
366  unsigned int t;
367  public:
370  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
371  : Test("DFS::"+Model::name()+"::"+
372  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
373  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
374  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
376  virtual bool run(void) {
377  Model* m = new Model(htb1,htb2,htb3);
380  o.c_d = c_d;
381  o.a_d = a_d;
382  o.threads = t;
383  o.stop = &f;
384  Gecode::DFS<Model> dfs(m,o);
385  int n = m->solutions();
386  delete m;
387  while (true) {
388  Model* s = dfs.next();
389  if (s != NULL) {
390  n--; delete s;
391  }
392  if ((s == NULL) && !dfs.stopped())
393  break;
394  f.limit(f.limit()+2);
395  }
396  return n == 0;
397  }
398  };
399 
401  template<class Model>
402  class LDS : public Test {
403  private:
405  unsigned int t;
406  public:
409  unsigned int t0)
410  : Test("LDS::"+Model::name()+"::"+
411  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
412  htb1,htb2,htb3), t(t0) {}
414  virtual bool run(void) {
415  Model* m = new Model(htb1,htb2,htb3);
418  o.threads = t;
419  o.d_l = 50;
420  o.stop = &f;
421  Gecode::LDS<Model> lds(m,o);
422  int n = m->solutions();
423  delete m;
424  while (true) {
425  Model* s = lds.next();
426  if (s != NULL) {
427  n--; delete s;
428  }
429  if ((s == NULL) && !lds.stopped())
430  break;
431  f.limit(f.limit()+2);
432  }
433  return n == 0;
434  }
435  };
436 
438  template<class Model>
439  class BAB : public Test {
440  private:
442  unsigned int c_d;
444  unsigned int a_d;
446  unsigned int t;
447  public:
450  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
451  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
452  : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
453  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
454  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
455  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
457  virtual bool run(void) {
458  Model* m = new Model(htb1,htb2,htb3,htc);
461  o.c_d = c_d;
462  o.a_d = a_d;
463  o.threads = t;
464  o.stop = &f;
465  Gecode::BAB<Model> bab(m,o);
466  delete m;
467  Model* b = NULL;
468  while (true) {
469  Model* s = bab.next();
470  if (s != NULL) {
471  delete b; b=s;
472  }
473  if ((s == NULL) && !bab.stopped())
474  break;
475  f.limit(f.limit()+2);
476  }
477  bool ok = (b == NULL) || b->best();
478  delete b;
479  return ok;
480  }
481  };
482 
484  template<class Model, template<class> class Engine>
485  class RBS : public Test {
486  private:
488  unsigned int t;
489  public:
491  RBS(const std::string& e, unsigned int t0)
492  : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
495  virtual bool run(void) {
496  Model* m = new Model(htb1,htb2,htb3);
499  o.threads = t;
500  o.stop = &f;
501  o.d_l = 100;
504  int n = m->solutions();
505  delete m;
506  while (true) {
507  Model* s = rbs.next();
508  if (s != NULL) {
509  n--; delete s;
510  }
511  if ((s == NULL) && !rbs.stopped())
512  break;
513  f.limit(f.limit()+2);
514  }
515  return n == 0;
516  }
517  };
518 
520  template<class Model, template<class> class Engine>
521  class PBS : public Test {
522  private:
524  bool best;
526  unsigned int a;
528  unsigned int t;
529  public:
531  PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
532  : Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
533  HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
535  virtual bool run(void) {
536  Model* m = new Model(htb1,htb2,htb3);
539  o.assets = a;
540  o.threads = t;
541  o.d_l = 100;
542  o.stop = &f;
544  if (best) {
545  Model* b = NULL;
546  while (true) {
547  Model* s = pbs.next();
548  if (s != NULL) {
549  delete b; b=s;
550  }
551  if ((s == NULL) && !pbs.stopped())
552  break;
553  f.limit(f.limit()+2);
554  }
555  bool ok = (b == NULL) || b->best();
556  delete b;
557  return ok;
558  } else {
559  int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
560  delete m;
561  while (true) {
562  Model* s = pbs.next();
563  if (s != NULL) {
564  n--; delete s;
565  }
566  if ((s == NULL) && !pbs.stopped())
567  break;
568  f.limit(f.limit()+2);
569  }
570  return n >= 0;
571  }
572  }
573  };
574 
576  template<class Model>
577  class SEBPBS : public Test {
578  private:
580  bool best;
582  unsigned int mt;
584  unsigned int st;
585  public:
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),
589  HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
591  virtual bool run(void) {
592  using namespace Gecode;
593  Model* m = new Model(htb1,htb2,htb3);
595 
597  mo.threads = mt;
598  mo.d_l = 100;
599  mo.stop = &f;
600 
602  so.threads = st;
603  so.d_l = 100;
605  if (best) {
606  SEBs sebs(3);
607  sebs[0] = bab<Model>(so);
608  sebs[1] = bab<Model>(so);
609  sebs[2] = rbs<Model,Gecode::BAB>(so);
610  Gecode::PBS<Model,Gecode::BAB> pbs(m, sebs, mo);
611  delete m;
612 
613  Model* b = NULL;
614  while (true) {
615  Model* s = pbs.next();
616  if (s != NULL) {
617  delete b; b=s;
618  }
619  if ((s == NULL) && !pbs.stopped())
620  break;
621  f.limit(f.limit()+2);
622  }
623  bool ok = (b == NULL) || b->best();
624  delete b;
625  return ok;
626  } else {
627  SEBs sebs(3);
628  sebs[0] = dfs<Model>(so);
629  sebs[1] = lds<Model>(so);
630  sebs[2] = rbs<Model,Gecode::DFS>(so);
631  Gecode::PBS<Model,Gecode::DFS> pbs(m, sebs, mo);
632 
633  int n = 3 * m->solutions();
634  delete m;
635 
636  while (true) {
637  Model* s = pbs.next();
638  if (s != NULL) {
639  n--; delete s;
640  }
641  if ((s == NULL) && !pbs.stopped())
642  break;
643  f.limit(f.limit()+2);
644  }
645  return n >= 0;
646  }
647  }
648  };
649 
651  class BranchTypes {
652  private:
654  static const HowToBranch htbs[3];
656  int i;
657  public:
659  BranchTypes(void) : i(0) {}
661  bool operator()(void) const {
662  return i<3;
663  }
665  void operator++(void) {
666  i++;
667  }
669  HowToBranch htb(void) const {
670  return htbs[i];
671  }
672  };
673 
674  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
675 
678  private:
680  static const HowToConstrain htcs[4];
682  int i;
683  public:
685  ConstrainTypes(void) : i(0) {}
687  bool operator()(void) const {
688  return i<4;
689  }
691  void operator++(void) {
692  i++;
693  }
695  HowToConstrain htc(void) const {
696  return htcs[i];
697  }
698  };
699 
700  const HowToConstrain ConstrainTypes::htcs[4] =
702 
703 
705  class Create {
706  public:
708  Create(void) {
709  // Depth-first search
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++) {
713  for (BranchTypes htb1; htb1(); ++htb1)
714  for (BranchTypes htb2; htb2(); ++htb2)
715  for (BranchTypes htb3; htb3(); ++htb3)
716  (void) new DFS<HasSolutions>
717  (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
719  c_d, a_d, t);
721  c_d, a_d, t);
723  c_d, a_d, t);
724  }
725 
726  // Limited discrepancy search
727  for (unsigned int t = 1; t<=4; t++) {
728  for (BranchTypes htb1; htb1(); ++htb1)
729  for (BranchTypes htb2; htb2(); ++htb2)
730  for (BranchTypes htb3; htb3(); ++htb3)
731  (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
732  ,t);
735  }
736 
737  // Best solution search
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++) {
741  for (ConstrainTypes htc; htc(); ++htc)
742  for (BranchTypes htb1; htb1(); ++htb1)
743  for (BranchTypes htb2; htb2(); ++htb2)
744  for (BranchTypes htb3; htb3(); ++htb3) {
745  (void) new BAB<HasSolutions>
746  (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
747  c_d,a_d,t);
748  }
749  (void) new BAB<FailImmediate>
751  (void) new BAB<SolveImmediate>
753  (void) new BAB<HasSolutions>
755  }
756  // Restart-based search
757  for (unsigned int t=1; t<=4; t++) {
758  (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
759  (void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
760  (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
761  (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
762  (void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
763  (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
764  (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
765  (void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
766  (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
767  }
768  // Portfolio-based search
769  for (unsigned int a=1; a<=4; a++)
770  for (unsigned int t=1; t<=2*a; t++) {
771  (void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
772  (void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
773  (void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
774  (void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
775  (void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
776  (void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
777  (void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
778  (void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
779  (void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
780  }
781  // Portfolio-based search using SEBs
782  for (unsigned int mt=1; mt<=3; mt += 2)
783  for (unsigned int st=1; st<=8; st++) {
784  (void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
785  (void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
786  (void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
787  (void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
788  (void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
789  (void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
790  }
791  }
792  };
793 
795  }
796 
797 }
798 
799 // STATISTICS: test-search
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl)
Post lexical order between x and y.
Definition: aliases.hpp:132
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
Definition: bool-expr.cpp:230
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:629
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Depth-first branch-and-bound search engine.
Definition: search.hh:1070
Passing Boolean variables.
Definition: int.hh:712
Depth-first search engine.
Definition: search.hh:1036
Passing integer variables.
Definition: int.hh:656
Integer variable array.
Definition: int.hh:763
Integer variables.
Definition: int.hh:371
Limited discrepancy search engine.
Definition: search.hh:1108
Information passed by meta search engines.
Definition: core.hpp:1613
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition: core.hpp:1620
@ RESTART
Information is provided by a restart-based engine.
Definition: core.hpp:1618
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3101
Type type(void) const
Return type of information.
Definition: core.hpp:3082
Meta engine using a portfolio of search engines.
Definition: search.hh:1236
Meta-engine performing restart-based search.
Definition: search.hh:1152
Passing search engine builder arguments.
Definition: search.hh:1002
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition: cutoff.cpp:160
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:148
Stop-object based on number of failures
Definition: search.hh:852
Search engine options
Definition: search.hh:746
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:757
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:767
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:755
Stop * stop
Stop object for stopping search.
Definition: search.hh:765
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:759
double threads
Number of threads to use.
Definition: search.hh:751
Computation spaces.
Definition: core.hpp:1742
Base class for all tests to be run
Definition: test.hh:103
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
virtual bool run(void)
Run test.
Definition: search.cpp:457
Iterator for branching types.
Definition: search.cpp:651
HowToBranch htb(void) const
Return current branching type.
Definition: search.cpp:669
BranchTypes(void)
Initialize iterator.
Definition: search.cpp:659
void operator++(void)
Increment to next branching type.
Definition: search.cpp:665
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:661
Iterator for constrain types.
Definition: search.cpp:677
HowToConstrain htc(void) const
Return current constrain type.
Definition: search.cpp:695
void operator++(void)
Increment to next constrain type.
Definition: search.cpp:691
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:687
ConstrainTypes(void)
Initialize iterator.
Definition: search.cpp:685
Help class to create and register tests.
Definition: search.cpp:705
Create(void)
Perform creation and registration.
Definition: search.cpp:708
virtual bool run(void)
Run test.
Definition: search.cpp:376
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition: search.cpp:369
Space that immediately fails.
Definition: search.cpp:95
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:121
IntVarArray x
Variables used.
Definition: search.cpp:98
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:100
FailImmediate(FailImmediate &s)
Constructor for cloning s.
Definition: search.cpp:106
static std::string name(void)
Return name.
Definition: search.cpp:125
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:117
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:114
virtual Space * copy(void)
Copy during cloning.
Definition: search.cpp:110
Space that requires propagation and has solutions.
Definition: search.cpp:166
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:245
static std::string name(void)
Return name.
Definition: search.cpp:285
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:257
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition: search.cpp:212
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
Definition: search.cpp:289
virtual Space * copy(void)
Copy during cloning.
Definition: search.cpp:208
HowToConstrain htc
How to constrain.
Definition: search.cpp:173
HasSolutions(HasSolutions &s)
Constructor for cloning s.
Definition: search.cpp:202
IntVarArray x
Variables used.
Definition: search.cpp:169
HowToBranch htb1
How to branch.
Definition: search.cpp:171
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:191
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition: search.cpp:175
virtual bool run(void)
Run test.
Definition: search.cpp:414
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Definition: search.cpp:408
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
Definition: search.cpp:531
virtual bool run(void)
Run test.
Definition: search.cpp:535
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition: search.cpp:491
virtual bool run(void)
Run test.
Definition: search.cpp:495
Test for portfolio-based search using SEBs
Definition: search.cpp:577
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
Definition: search.cpp:587
virtual bool run(void)
Run test.
Definition: search.cpp:591
Space that is immediately solved.
Definition: search.cpp:131
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:152
IntVarArray x
Variables used.
Definition: search.cpp:134
virtual Space * copy(void)
Copy during cloning.
Definition: search.cpp:144
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:156
static std::string name(void)
Return name.
Definition: search.cpp:160
SolveImmediate(SolveImmediate &s)
Constructor for cloning s.
Definition: search.cpp:140
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:136
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:148
Space with information.
Definition: search.cpp:72
virtual int solutions(void) const =0
Return number of solutions.
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
Definition: search.cpp:83
TestSpace(void)
Constructor for space creation.
Definition: search.cpp:75
TestSpace(TestSpace &s)
Constructor for cloning s.
Definition: search.cpp:77
virtual bool best(void) const =0
Verify that this is best solution.
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition: search.cpp:319
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition: search.cpp:350
HowToConstrain htc
How to constrain.
Definition: search.cpp:317
static std::string str(HowToBranch htb)
Map branching to string.
Definition: search.cpp:325
HowToBranch htb1
How to branch.
Definition: search.cpp:315
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition: search.cpp:337
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:41
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:208
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:203
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with variable selection vars and value selection vals.
Definition: branch.cpp:111
void 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:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
@ IRT_EQ
Equality ( )
Definition: int.hh:926
@ IRT_LE
Less ( )
Definition: int.hh:929
@ IRT_GR
Greater ( )
Definition: int.hh:931
@ IRT_LQ
Less or equal ( )
Definition: int.hh:928
@ BOT_AND
Conjunction.
Definition: int.hh:951
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:309
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
Definition: lds.hpp:74
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:111
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:55
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:100
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Finite domain integers.
Definition: abs.hpp:38
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
Gecode::IntArgs i({1, 2, 3, 4})
HowToBranch
Values for selecting branchers.
Definition: search.cpp:48
@ HTB_BINARY
Branch with two alternatives.
Definition: search.cpp:51
@ HTB_NONE
Do not branch.
Definition: search.cpp:49
@ HTB_UNARY
Branch with single alternative.
Definition: search.cpp:50
@ HTB_NARY
Branch with many alternatives.
Definition: search.cpp:52
HowToConstrain
Values for selecting how to constrain.
Definition: search.cpp:56
@ HTC_BAL_GR
Constrain for largest balance.
Definition: search.cpp:61
@ HTC_LEX_LE
Constrain for lexically smallest.
Definition: search.cpp:58
@ HTC_LEX_GR
Constrain for lexically biggest.
Definition: search.cpp:59
@ HTC_BAL_LE
Constrain for smallest balance.
Definition: search.cpp:60
@ HTC_NONE
Do not constrain.
Definition: search.cpp:57
Create c
Definition: search.cpp:794
WhichModel
Values for selecting models.
Definition: search.cpp:65
@ WM_FAIL_SEARCH
Model without solutions.
Definition: search.cpp:67
@ WM_SOLUTIONS
Model with solutions.
Definition: search.cpp:68
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
Definition: search.cpp:66
General test support.
Definition: afc.cpp:39
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56