Generated on Sat May 25 2013 18:00:42 for Gecode by doxygen 1.8.3.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: 2013-03-07 22:14:40 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13467 $
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 HasSolutions : public TestSpace {
126  public:
130  HowToBranch htb1, htb2, htb3;
134  void branch(const IntVarArgs& x, HowToBranch htb) {
135  switch (htb) {
136  case HTB_NONE:
137  break;
138  case HTB_UNARY:
139  assign(*this, x, INT_ASSIGN_MIN());
140  break;
141  case HTB_BINARY:
142  Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
143  break;
144  case HTB_NARY:
146  break;
147  }
148  }
152  : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
153  distinct(*this, x);
154  rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
155  rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
156  IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
157  IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
158  IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
159  }
161  HasSolutions(bool share, HasSolutions& s)
162  : TestSpace(share,s),
163  htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
164  x.update(*this, share, s.x);
165  }
167  virtual Space* copy(bool share) {
168  return new HasSolutions(share,*this);
169  }
171  virtual void constrain(const Space& _s) {
172  const HasSolutions& s = static_cast<const HasSolutions&>(_s);
173  switch (htc) {
174  case HTC_NONE:
175  break;
176  case HTC_LEX_LE:
177  case HTC_LEX_GR:
178  {
179  IntVarArgs y(6);
180  for (int i=0; i<6; i++)
181  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
182  lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
183  break;
184  }
185  case HTC_BAL_LE:
186  case HTC_BAL_GR:
187  {
188  IntVarArgs y(6);
189  for (int i=0; i<6; i++)
190  y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
191  IntVar xs(*this, -18, 18);
192  IntVar ys(*this, -18, 18);
193  rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
194  rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
195  rel(*this,
196  expr(*this,abs(xs)),
197  (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
198  expr(*this,abs(ys)));
199  break;
200  }
201  }
202  }
204  virtual int solutions(void) const {
205  if (htb1 == HTB_NONE) {
206  assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
207  return 1;
208  }
209  if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
210  return 0;
211  if (htb3 == HTB_UNARY)
212  return 4;
213  return 8;
214  }
216  virtual bool best(void) const {
217  if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
218  (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
219  return true;
220  switch (htc) {
221  case HTC_NONE:
222  return true;
223  case HTC_LEX_LE:
224  return ((x[0].val()==4) && (x[1].val()==5) &&
225  (x[2].val()==2) && (x[3].val()==3) &&
226  (x[4].val()==0) && (x[5].val()==1));
227  case HTC_LEX_GR:
228  return ((x[0].val()==5) && (x[1].val()==4) &&
229  (x[2].val()==3) && (x[3].val()==2) &&
230  (x[4].val()==1) && (x[5].val()==0));
231  case HTC_BAL_LE:
232  return ((x[0].val()==4) && (x[1].val()==5) &&
233  (x[2].val()==2) && (x[3].val()==3) &&
234  (x[4].val()==0) && (x[5].val()==1));
235  case HTC_BAL_GR:
236  return ((x[0].val()==4) && (x[1].val()==5) &&
237  (x[2].val()==3) && (x[3].val()==2) &&
238  (x[4].val()==0) && (x[5].val()==1));
239  default: GECODE_NEVER;
240  }
241  return false;
242  }
244  static std::string name(void) {
245  return "Sol";
246  }
248  virtual void master(unsigned long int i, const Space* _s) {
249  const HasSolutions* s = static_cast<const HasSolutions*>(_s);
250  if (s != NULL) {
251  BoolVarArgs b;
252  for (int i=0; i<x.size(); i++)
253  b << expr(*this, x[i] == s->x[i]);
254  rel(*this, BOT_AND, b, 0);
255  }
256  }
257  };
258 
260  class Test : public Base {
261  public:
263  HowToBranch htb1, htb2, htb3;
267  static std::string str(unsigned int i) {
268  std::stringstream s;
269  s << i;
270  return s.str();
271  }
273  static std::string str(HowToBranch htb) {
274  switch (htb) {
275  case HTB_NONE: return "None";
276  case HTB_UNARY: return "Unary";
277  case HTB_BINARY: return "Binary";
278  case HTB_NARY: return "Nary";
279  default: GECODE_NEVER;
280  }
281  GECODE_NEVER;
282  return "";
283  }
285  static std::string str(HowToConstrain htc) {
286  switch (htc) {
287  case HTC_NONE: return "None";
288  case HTC_LEX_LE: return "LexLe";
289  case HTC_LEX_GR: return "LexGr";
290  case HTC_BAL_LE: return "BalLe";
291  case HTC_BAL_GR: return "BalGr";
292  default: GECODE_NEVER;
293  }
294  GECODE_NEVER;
295  return "";
296  }
298  Test(const std::string& s,
299  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
301  : Base("Search::"+s),
302  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
303  };
304 
306  template<class Model>
307  class DFS : public Test {
308  private:
310  unsigned int c_d;
312  unsigned int a_d;
314  unsigned int t;
315  public:
318  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
319  : Test("DFS::"+Model::name()+"::"+
320  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
321  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
322  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
324  virtual bool run(void) {
325  Model* m = new Model(htb1,htb2,htb3);
328  o.c_d = c_d;
329  o.a_d = a_d;
330  o.threads = t;
331  o.stop = &f;
332  Gecode::DFS<Model> dfs(m,o);
333  int n = m->solutions();
334  delete m;
335  while (true) {
336  Model* s = dfs.next();
337  if (s != NULL) {
338  n--; delete s;
339  }
340  if ((s == NULL) && !dfs.stopped())
341  break;
342  f.limit(f.limit()+2);
343  }
344  return n == 0;
345  }
346  };
347 
349  template<class Model, template<class> class Engine>
350  class Best : public Test {
351  private:
353  unsigned int c_d;
355  unsigned int a_d;
357  unsigned int t;
358  public:
360  Best(const std::string& b, HowToConstrain htc,
361  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
362  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
363  : Test(b+"::"+Model::name()+"::"+str(htc)+"::"+
364  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
365  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
366  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
368  virtual bool run(void) {
369  Model* m = new Model(htb1,htb2,htb3,htc);
372  o.c_d = c_d;
373  o.a_d = a_d;
374  o.threads = t;
375  o.stop = &f;
376  Engine<Model> best(m,o);
377  delete m;
378  Model* b = NULL;
379  while (true) {
380  Model* s = best.next();
381  if (s != NULL) {
382  delete b; b=s;
383  }
384  if ((s == NULL) && !best.stopped())
385  break;
386  f.limit(f.limit()+2);
387  }
388  bool ok = (b == NULL) || b->best();
389  delete b;
390  return ok;
391  }
392  };
393 
395  template<class Model, template<class> class Engine>
396  class RBS : public Test {
397  private:
399  unsigned int t;
400  public:
402  RBS(const std::string& e, unsigned int t0)
403  : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
406  virtual bool run(void) {
407  Model* m = new Model(htb1,htb2,htb3);
410  o.threads = t;
411  o.stop = &f;
414  int n = m->solutions();
415  delete m;
416  while (true) {
417  Model* s = rbs.next();
418  if (s != NULL) {
419  n--; delete s;
420  }
421  if ((s == NULL) && !rbs.stopped())
422  break;
423  f.limit(f.limit()+2);
424  }
425  return n == 0;
426  }
427  };
428 
430  class BranchTypes {
431  private:
433  static const HowToBranch htbs[3];
435  int i;
436  public:
438  BranchTypes(void) : i(0) {}
440  bool operator()(void) const {
441  return i<3;
442  }
444  void operator++(void) {
445  i++;
446  }
448  HowToBranch htb(void) const {
449  return htbs[i];
450  }
451  };
452 
453  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
454 
457  private:
459  static const HowToConstrain htcs[4];
461  int i;
462  public:
464  ConstrainTypes(void) : i(0) {}
466  bool operator()(void) const {
467  return i<4;
468  }
470  void operator++(void) {
471  i++;
472  }
474  HowToConstrain htc(void) const {
475  return htcs[i];
476  }
477  };
478 
479  const HowToConstrain ConstrainTypes::htcs[4] =
481 
482 
484  class Create {
485  public:
487  Create(void) {
488  // Depth-first search
489  for (unsigned int t = 1; t<=4; t++)
490  for (unsigned int c_d = 1; c_d<10; c_d++)
491  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
492  for (BranchTypes htb1; htb1(); ++htb1)
493  for (BranchTypes htb2; htb2(); ++htb2)
494  for (BranchTypes htb3; htb3(); ++htb3)
495  (void) new DFS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb(),
496  c_d, a_d, t);
498  c_d, a_d, t);
500  c_d, a_d, t);
501  }
502 
503  // Best solution search
504  for (unsigned int t = 1; t<=4; t++)
505  for (unsigned int c_d = 1; c_d<10; c_d++)
506  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
507  for (ConstrainTypes htc; htc(); ++htc)
508  for (BranchTypes htb1; htb1(); ++htb1)
509  for (BranchTypes htb2; htb2(); ++htb2)
510  for (BranchTypes htb3; htb3(); ++htb3) {
511  (void) new Best<HasSolutions,BAB>
512  ("BAB",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
513  c_d,a_d,t);
514  }
515  (void) new Best<FailImmediate,BAB>
517  (void) new Best<HasSolutions,BAB>
519  }
520  // Restart-based search
521  for (unsigned int t = 1; t<=4; t++) {
522  (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
523  (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
524  }
525  }
526  };
527 
529  }
530 
531 }
532 
533 // STATISTICS: test-search