Generated on Sat Jul 28 2018 17:20:14 for Gecode by doxygen 1.8.14
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: 2017-03-28 16:18:06 +0200 (Tue, 28 Mar 2017) $ by $Author: schulte $
11  * $Revision: 15620 $
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 MetaInfo& mi) {
88  if (mi.type() == MetaInfo::RESTART) {
89  if (mi.last() != NULL)
90  constrain(*mi.last());
91  return false;
92  } else {
93  return false;
94  }
95  }
96  };
97 
99  class FailImmediate : public TestSpace {
100  public:
106  : x(*this,1,0,0) {
107  rel(*this, x[0], IRT_EQ, 1);
108  }
110  FailImmediate(bool share, FailImmediate& s) : TestSpace(share,s) {
111  x.update(*this, share, s.x);
112  }
114  virtual Space* copy(bool share) {
115  return new FailImmediate(share,*this);
116  }
118  virtual void constrain(const Space&) {
119  }
121  virtual int solutions(void) const {
122  return 0;
123  }
125  virtual bool best(void) const {
126  return false;
127  }
129  static std::string name(void) {
130  return "Fail";
131  }
132  };
133 
135  class SolveImmediate : public TestSpace {
136  public:
142  : x(*this,1,0,0) {}
144  SolveImmediate(bool share, SolveImmediate& s) : TestSpace(share,s) {
145  x.update(*this, share, s.x);
146  }
148  virtual Space* copy(bool share) {
149  return new SolveImmediate(share,*this);
150  }
152  virtual void constrain(const Space&) {
153  fail();
154  }
156  virtual int solutions(void) const {
157  return 1;
158  }
160  virtual bool best(void) const {
161  return true;
162  }
164  static std::string name(void) {
165  return "Solve";
166  }
167  };
168 
170  class HasSolutions : public TestSpace {
171  public:
175  HowToBranch htb1, htb2, htb3;
179  void branch(const IntVarArgs& x, HowToBranch htb) {
180  switch (htb) {
181  case HTB_NONE:
182  break;
183  case HTB_UNARY:
184  assign(*this, x, INT_ASSIGN_MIN());
185  break;
186  case HTB_BINARY:
188  break;
189  case HTB_NARY:
191  break;
192  }
193  }
197  : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
198  distinct(*this, x);
199  rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
200  rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
201  IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
202  IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
203  IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
204  }
206  HasSolutions(bool share, HasSolutions& s)
207  : TestSpace(share,s),
208  htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
209  x.update(*this, share, s.x);
210  }
212  virtual Space* copy(bool share) {
213  return new HasSolutions(share,*this);
214  }
216  virtual void constrain(const Space& _s) {
217  const HasSolutions& s = static_cast<const HasSolutions&>(_s);
218  switch (htc) {
219  case HTC_NONE:
220  break;
221  case HTC_LEX_LE:
222  case HTC_LEX_GR:
223  {
224  IntVarArgs y(6);
225  for (int i=0; i<6; i++)
226  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
227  lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
228  break;
229  }
230  case HTC_BAL_LE:
231  case HTC_BAL_GR:
232  {
233  IntVarArgs y(6);
234  for (int i=0; i<6; i++)
235  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
236  IntVar xs(*this, -18, 18);
237  IntVar ys(*this, -18, 18);
238  rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
239  rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
240  rel(*this,
241  expr(*this,abs(xs)),
242  (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
243  expr(*this,abs(ys)));
244  break;
245  }
246  }
247  }
249  virtual int solutions(void) const {
250  if (htb1 == HTB_NONE) {
251  assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
252  return 1;
253  }
254  if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
255  return 0;
256  if (htb3 == HTB_UNARY)
257  return 4;
258  return 8;
259  }
261  virtual bool best(void) const {
262  if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
263  (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
264  return true;
265  switch (htc) {
266  case HTC_NONE:
267  return true;
268  case HTC_LEX_LE:
269  return ((x[0].val()==4) && (x[1].val()==5) &&
270  (x[2].val()==2) && (x[3].val()==3) &&
271  (x[4].val()==0) && (x[5].val()==1));
272  case HTC_LEX_GR:
273  return ((x[0].val()==5) && (x[1].val()==4) &&
274  (x[2].val()==3) && (x[3].val()==2) &&
275  (x[4].val()==1) && (x[5].val()==0));
276  case HTC_BAL_LE:
277  return ((x[0].val()==4) && (x[1].val()==5) &&
278  (x[2].val()==2) && (x[3].val()==3) &&
279  (x[4].val()==0) && (x[5].val()==1));
280  case HTC_BAL_GR:
281  return ((x[0].val()==4) && (x[1].val()==5) &&
282  (x[2].val()==3) && (x[3].val()==2) &&
283  (x[4].val()==0) && (x[5].val()==1));
284  default: GECODE_NEVER;
285  }
286  return false;
287  }
289  static std::string name(void) {
290  return "Sol";
291  }
293  virtual bool master(const MetaInfo& mi) {
294  switch (mi.type()) {
295  case MetaInfo::RESTART:
296  if (mi.last() != NULL) {
297  const HasSolutions* s
298  = static_cast<const HasSolutions*>(mi.last());
299  BoolVarArgs b;
300  for (int i=0; i<x.size(); i++)
301  b << expr(*this, x[i] == s->x[i]);
302  rel(*this, BOT_AND, b, 0);
303  }
304  break;
305  case MetaInfo::PORTFOLIO:
306  // Do not kill the brancher!
307  break;
308  default:
309  break;
310  }
311  return false;
312  }
313  };
314 
316  class Test : public Base {
317  public:
319  HowToBranch htb1, htb2, htb3;
323  static std::string str(unsigned int i) {
324  std::stringstream s;
325  s << i;
326  return s.str();
327  }
329  static std::string str(HowToBranch htb) {
330  switch (htb) {
331  case HTB_NONE: return "None";
332  case HTB_UNARY: return "Unary";
333  case HTB_BINARY: return "Binary";
334  case HTB_NARY: return "Nary";
335  default: GECODE_NEVER;
336  }
337  GECODE_NEVER;
338  return "";
339  }
341  static std::string str(HowToConstrain htc) {
342  switch (htc) {
343  case HTC_NONE: return "None";
344  case HTC_LEX_LE: return "LexLe";
345  case HTC_LEX_GR: return "LexGr";
346  case HTC_BAL_LE: return "BalLe";
347  case HTC_BAL_GR: return "BalGr";
348  default: GECODE_NEVER;
349  }
350  GECODE_NEVER;
351  return "";
352  }
354  Test(const std::string& s,
355  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
357  : Base("Search::"+s),
358  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
359  };
360 
362  template<class Model>
363  class DFS : public Test {
364  private:
366  unsigned int c_d;
368  unsigned int a_d;
370  unsigned int t;
371  public:
374  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
375  : Test("DFS::"+Model::name()+"::"+
376  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
377  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
378  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
380  virtual bool run(void) {
381  Model* m = new Model(htb1,htb2,htb3);
384  o.c_d = c_d;
385  o.a_d = a_d;
386  o.threads = t;
387  o.stop = &f;
388  Gecode::DFS<Model> dfs(m,o);
389  int n = m->solutions();
390  delete m;
391  while (true) {
392  Model* s = dfs.next();
393  if (s != NULL) {
394  n--; delete s;
395  }
396  if ((s == NULL) && !dfs.stopped())
397  break;
398  f.limit(f.limit()+2);
399  }
400  return n == 0;
401  }
402  };
403 
405  template<class Model>
406  class LDS : public Test {
407  private:
409  unsigned int t;
410  public:
413  unsigned int t0)
414  : Test("LDS::"+Model::name()+"::"+
415  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
416  htb1,htb2,htb3), t(t0) {}
418  virtual bool run(void) {
419  Model* m = new Model(htb1,htb2,htb3);
422  o.threads = t;
423  o.d_l = 50;
424  o.stop = &f;
425  Gecode::LDS<Model> lds(m,o);
426  int n = m->solutions();
427  delete m;
428  while (true) {
429  Model* s = lds.next();
430  if (s != NULL) {
431  n--; delete s;
432  }
433  if ((s == NULL) && !lds.stopped())
434  break;
435  f.limit(f.limit()+2);
436  }
437  return n == 0;
438  }
439  };
440 
442  template<class Model>
443  class BAB : public Test {
444  private:
446  unsigned int c_d;
448  unsigned int a_d;
450  unsigned int t;
451  public:
454  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
455  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
456  : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
457  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
458  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
459  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
461  virtual bool run(void) {
462  Model* m = new Model(htb1,htb2,htb3,htc);
465  o.c_d = c_d;
466  o.a_d = a_d;
467  o.threads = t;
468  o.stop = &f;
469  Gecode::BAB<Model> bab(m,o);
470  delete m;
471  Model* b = NULL;
472  while (true) {
473  Model* s = bab.next();
474  if (s != NULL) {
475  delete b; b=s;
476  }
477  if ((s == NULL) && !bab.stopped())
478  break;
479  f.limit(f.limit()+2);
480  }
481  bool ok = (b == NULL) || b->best();
482  delete b;
483  return ok;
484  }
485  };
486 
488  template<class Model, template<class> class Engine>
489  class RBS : public Test {
490  private:
492  unsigned int t;
493  public:
495  RBS(const std::string& e, unsigned int t0)
496  : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
499  virtual bool run(void) {
500  Model* m = new Model(htb1,htb2,htb3);
503  o.threads = t;
504  o.stop = &f;
505  o.d_l = 100;
508  int n = m->solutions();
509  delete m;
510  while (true) {
511  Model* s = rbs.next();
512  if (s != NULL) {
513  n--; delete s;
514  }
515  if ((s == NULL) && !rbs.stopped())
516  break;
517  f.limit(f.limit()+2);
518  }
519  return n == 0;
520  }
521  };
522 
524  template<class Model, template<class> class Engine>
525  class PBS : public Test {
526  private:
528  bool best;
530  unsigned int a;
532  unsigned int t;
533  public:
535  PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
536  : Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
537  HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
539  virtual bool run(void) {
540  Model* m = new Model(htb1,htb2,htb3);
543  o.assets = a;
544  o.threads = t;
545  o.d_l = 100;
546  o.stop = &f;
548  if (best) {
549  Model* b = NULL;
550  while (true) {
551  Model* s = pbs.next();
552  if (s != NULL) {
553  delete b; b=s;
554  }
555  if ((s == NULL) && !pbs.stopped())
556  break;
557  f.limit(f.limit()+2);
558  }
559  bool ok = (b == NULL) || b->best();
560  delete b;
561  return ok;
562  } else {
563  int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
564  delete m;
565  while (true) {
566  Model* s = pbs.next();
567  if (s != NULL) {
568  n--; delete s;
569  }
570  if ((s == NULL) && !pbs.stopped())
571  break;
572  f.limit(f.limit()+2);
573  }
574  return n == 0;
575  }
576  }
577  };
578 
580  template<class Model>
581  class SEBPBS : public Test {
582  private:
584  bool best;
586  unsigned int mt;
588  unsigned int st;
589  public:
591  SEBPBS(const std::string& e, bool b, unsigned int mt0, unsigned int st0)
592  : Test("PBS::SEB::"+e+"::"+Model::name()+"::"+str(mt0)+"::"+str(st0),
593  HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
595  virtual bool run(void) {
596  using namespace Gecode;
597  Model* m = new Model(htb1,htb2,htb3);
599 
601  mo.threads = mt;
602  mo.d_l = 100;
603  mo.stop = &f;
604 
606  so.threads = st;
607  so.d_l = 100;
609  if (best) {
610  SEBs sebs(3);
611  sebs[0] = bab<Model>(so);
612  sebs[1] = bab<Model>(so);
613  sebs[2] = rbs<Model,Gecode::BAB>(so);
614  Gecode::PBS<Model,Gecode::BAB> pbs(m, sebs, mo);
615  delete m;
616 
617  Model* b = NULL;
618  while (true) {
619  Model* s = pbs.next();
620  if (s != NULL) {
621  delete b; b=s;
622  }
623  if ((s == NULL) && !pbs.stopped())
624  break;
625  f.limit(f.limit()+2);
626  }
627  bool ok = (b == NULL) || b->best();
628  delete b;
629  return ok;
630  } else {
631  SEBs sebs(3);
632  sebs[0] = dfs<Model>(so);
633  sebs[1] = lds<Model>(so);
634  sebs[2] = rbs<Model,Gecode::DFS>(so);
635  Gecode::PBS<Model,Gecode::DFS> pbs(m, sebs, mo);
636 
637  int n = 3 * m->solutions();
638  delete m;
639 
640  while (true) {
641  Model* s = pbs.next();
642  if (s != NULL) {
643  n--; delete s;
644  }
645  if ((s == NULL) && !pbs.stopped())
646  break;
647  f.limit(f.limit()+2);
648  }
649  return n == 0;
650  }
651  }
652  };
653 
655  class BranchTypes {
656  private:
658  static const HowToBranch htbs[3];
660  int i;
661  public:
663  BranchTypes(void) : i(0) {}
665  bool operator()(void) const {
666  return i<3;
667  }
669  void operator++(void) {
670  i++;
671  }
673  HowToBranch htb(void) const {
674  return htbs[i];
675  }
676  };
677 
678  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
679 
682  private:
684  static const HowToConstrain htcs[4];
686  int i;
687  public:
689  ConstrainTypes(void) : i(0) {}
691  bool operator()(void) const {
692  return i<4;
693  }
695  void operator++(void) {
696  i++;
697  }
699  HowToConstrain htc(void) const {
700  return htcs[i];
701  }
702  };
703 
704  const HowToConstrain ConstrainTypes::htcs[4] =
706 
707 
709  class Create {
710  public:
712  Create(void) {
713  // Depth-first search
714  for (unsigned int t = 1; t<=4; t++)
715  for (unsigned int c_d = 1; c_d<10; c_d++)
716  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
717  for (BranchTypes htb1; htb1(); ++htb1)
718  for (BranchTypes htb2; htb2(); ++htb2)
719  for (BranchTypes htb3; htb3(); ++htb3)
720  (void) new DFS<HasSolutions>
721  (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
723  c_d, a_d, t);
725  c_d, a_d, t);
727  c_d, a_d, t);
728  }
729 
730  // Limited discrepancy search
731  for (unsigned int t = 1; t<=4; t++) {
732  for (BranchTypes htb1; htb1(); ++htb1)
733  for (BranchTypes htb2; htb2(); ++htb2)
734  for (BranchTypes htb3; htb3(); ++htb3)
735  (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
736  ,t);
739  }
740 
741  // Best solution search
742  for (unsigned int t = 1; t<=4; t++)
743  for (unsigned int c_d = 1; c_d<10; c_d++)
744  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
745  for (ConstrainTypes htc; htc(); ++htc)
746  for (BranchTypes htb1; htb1(); ++htb1)
747  for (BranchTypes htb2; htb2(); ++htb2)
748  for (BranchTypes htb3; htb3(); ++htb3) {
749  (void) new BAB<HasSolutions>
750  (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
751  c_d,a_d,t);
752  }
753  (void) new BAB<FailImmediate>
755  (void) new BAB<SolveImmediate>
757  (void) new BAB<HasSolutions>
759  }
760  // Restart-based search
761  for (unsigned int t=1; t<=4; t++) {
762  (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
763  (void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
764  (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
765  (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
766  (void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
767  (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
768  (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
769  (void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
770  (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
771  }
772  // Portfolio-based search
773  for (unsigned int a=1; a<=4; a++)
774  for (unsigned int t=1; t<=2*a; t++) {
775  (void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
776  (void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
777  (void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
778  (void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
779  (void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
780  (void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
781  (void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
782  (void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
783  (void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
784  }
785  // Portfolio-based search using SEBs
786  for (unsigned int mt=1; mt<=3; mt += 2)
787  for (unsigned int st=1; st<=8; st++) {
788  (void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
789  (void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
790  (void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
791  (void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
792  (void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
793  (void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
794  }
795  }
796  };
797 
799  }
800 
801 }
802 
803 // STATISTICS: test-search
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:455
Model with solutions.
Definition: search.cpp:72
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:140
Iterator for branching types.
Definition: search.cpp:655
IntVarArray x
Variables used.
Definition: search.cpp:102
NodeType t
Type of node.
Definition: bool-expr.cpp:234
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:100
Limited discrepancy search engine.
Definition: search.hh:811
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
Definition: minimodel.hh:1854
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
Definition: search.cpp:591
static std::string name(void)
Return name.
Definition: search.cpp:289
FailImmediate(bool share, FailImmediate &s)
Constructor for cloning s.
Definition: search.cpp:110
TestSpace(bool share, TestSpace &s)
Constructor for cloning s.
Definition: search.cpp:81
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:114
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:43
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:261
Meta-engine performing restart-based search.
Definition: search.hh:855
Meta engine using a portfolio of search engines.
Definition: search.hh:939
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:453
Search engine options
Definition: search.hh:446
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition: search.cpp:341
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:453
HasSolutions(bool share, HasSolutions &s)
Constructor for cloning s.
Definition: search.cpp:206
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:45
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:125
Less or equal ( )
Definition: int.hh:909
Conjunction.
Definition: int.hh:932
HowToConstrain htc
How to constrain.
Definition: search.cpp:321
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:152
Information is provided by a restart-based engine.
Definition: core.hpp:1625
Integer variable array.
Definition: int.hh:744
HowToConstrain htc(void) const
Return current constrain type.
Definition: search.cpp:699
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition: search.cpp:373
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:148
void operator++(void)
Increment to next branching type.
Definition: search.cpp:669
Greater ( )
Definition: int.hh:912
HowToConstrain htc
How to constrain.
Definition: search.cpp:177
virtual bool run(void)
Run test.
Definition: search.cpp:595
Computation spaces.
Definition: core.hpp:1748
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:457
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition: search.cpp:179
Create c
Definition: search.cpp:798
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
static std::string name(void)
Return name.
Definition: search.cpp:129
Create(void)
Perform creation and registration.
Definition: search.cpp:712
virtual Space * copy(bool share)
Copy during cloning.
Definition: search.cpp:212
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition: search.cpp:354
Model that fails immediately.
Definition: search.cpp:70
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:471
double threads
Number of threads to use.
Definition: search.hh:451
Constrain for lexically smallest.
Definition: search.cpp:62
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
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:907
virtual bool run(void)
Run test.
Definition: search.cpp:499
static std::string str(HowToBranch htb)
Map branching to string.
Definition: search.cpp:329
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:773
Model without solutions.
Definition: search.cpp:71
Space that immediately fails.
Definition: search.cpp:99
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3203
void operator++(void)
Increment to next constrain type.
Definition: search.cpp:695
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Definition: search.cpp:412
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition: search.cpp:323
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:111
WhichModel
Values for selecting models.
Definition: search.cpp:69
Branch with two alternatives.
Definition: search.cpp:55
Type type(void) const
Return type of information.
Definition: core.hpp:3184
HowToBranch htb(void) const
Return current branching type.
Definition: search.cpp:673
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:104
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:59
HowToBranch htb3
Definition: search.cpp:319
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
TestSpace(void)
Constructor for space creation.
Definition: search.cpp:79
Base class for all tests to be run
Definition: test.hh:107
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:50
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
Definition: search.cpp:293
virtual bool run(void)
Run test.
Definition: search.cpp:539
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:156
static std::string name(void)
Return name.
Definition: search.cpp:164
Less ( )
Definition: int.hh:910
Information is provided by a portfolio-based engine.
Definition: core.hpp:1627
Space that is immediately solved.
Definition: search.cpp:135
Branch with many alternatives.
Definition: search.cpp:56
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition: cutoff.cpp:164
Passing integer variables.
Definition: int.hh:639
Passing Boolean variables.
Definition: int.hh:693
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
Definition: search.cpp:87
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:463
Space that requires propagation and has solutions.
Definition: search.cpp:170
Branch with single alternative.
Definition: search.cpp:54
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:322
General test support.
Definition: afc.cpp:43
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
virtual bool run(void)
Run test.
Definition: search.cpp:418
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:104
Iterator for constrain types.
Definition: search.cpp:681
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:709
HowToConstrain
Values for selecting how to constrain.
Definition: search.cpp:60
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition: search.cpp:195
ConstrainTypes(void)
Initialize iterator.
Definition: search.cpp:689
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
IntVarArray x
Variables used.
Definition: search.cpp:173
Integer variables.
Definition: int.hh:353
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:665
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
Definition: search.cpp:535
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:461
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
Space with information.
Definition: search.cpp:76
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:109
BranchTypes(void)
Initialize iterator.
Definition: search.cpp:663
Do not constrain.
Definition: search.cpp:61
Passing search engine builder arguments.
Definition: search.hh:704
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:249
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:152
Stop * stop
Stop object for stopping search.
Definition: search.hh:469
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition: search.cpp:216
virtual bool run(void)
Run test.
Definition: search.cpp:380
Gecode toplevel namespace
Information passed by meta search engines.
Definition: core.hpp:1620
Finite domain integers.
Definition: abs.hpp:42
Constrain for largest balance.
Definition: search.cpp:65
Test for portfolio-based search using SEBs
Definition: search.cpp:581
virtual bool best(void) const
Verify that this is best solution.
Definition: search.cpp:160
Do not branch.
Definition: search.cpp:53
SolveImmediate(bool share, SolveImmediate &s)
Constructor for cloning s.
Definition: search.cpp:144
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:115
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition: search.cpp:118
bool operator()(void) const
Test whether iterator is done.
Definition: search.cpp:691
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition: search.cpp:495
Engine * lds(Space *s, const Options &o)
Create lds engine.
Definition: lds.cpp:48
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition: rbs.hpp:114
Depth-first search engine.
Definition: search.hh:739
Stop-object based on number of failures
Definition: search.hh:554
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:416
virtual int solutions(void) const
Return number of solutions.
Definition: search.cpp:121
IntVarArray x
Variables used.
Definition: search.cpp:138
virtual bool stopped(void) const =0
Check whether engine has been stopped.