Generated on Fri Aug 31 2012 16:21:56 for Gecode by doxygen 1.8.1.2
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: 2010-10-09 22:58:12 +1100 (Sat, 09 Oct 2010) $ by $Author: schulte $
11  * $Revision: 11498 $
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:
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  }
247  };
248 
250  class Test : public Base {
251  public:
253  HowToBranch htb1, htb2, htb3;
257  static std::string str(unsigned int i) {
258  std::stringstream s;
259  s << i;
260  return s.str();
261  }
263  static std::string str(HowToBranch htb) {
264  switch (htb) {
265  case HTB_NONE: return "None";
266  case HTB_UNARY: return "Unary";
267  case HTB_BINARY: return "Binary";
268  case HTB_NARY: return "Nary";
269  default: GECODE_NEVER;
270  }
271  GECODE_NEVER;
272  return "";
273  }
275  static std::string str(HowToConstrain htc) {
276  switch (htc) {
277  case HTC_NONE: return "None";
278  case HTC_LEX_LE: return "LexLe";
279  case HTC_LEX_GR: return "LexGr";
280  case HTC_BAL_LE: return "BalLe";
281  case HTC_BAL_GR: return "BalGr";
282  default: GECODE_NEVER;
283  }
284  GECODE_NEVER;
285  return "";
286  }
288  Test(const std::string& s,
289  HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
291  : Base("Search::"+s),
292  htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
293  };
294 
296  template<class Model>
297  class DFS : public Test {
298  private:
300  unsigned int c_d;
302  unsigned int a_d;
304  unsigned int t;
305  public:
308  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
309  : Test("DFS::"+Model::name()+"::"+
310  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
311  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
312  htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
314  virtual bool run(void) {
315  Model* m = new Model(htb1,htb2,htb3);
318  o.c_d = c_d;
319  o.a_d = a_d;
320  o.threads = t;
321  o.stop = &f;
322  Gecode::DFS<Model> dfs(m,o);
323  int n = m->solutions();
324  delete m;
325  while (true) {
326  Model* s = dfs.next();
327  if (s != NULL) {
328  n--; delete s;
329  }
330  if ((s == NULL) && !dfs.stopped())
331  break;
332  f.limit(f.limit()+2);
333  }
334  return n == 0;
335  }
336  };
337 
339  template<class Model, template<class> class Engine>
340  class Best : public Test {
341  private:
343  unsigned int c_d;
345  unsigned int a_d;
347  unsigned int t;
348  public:
350  Best(const std::string& b, HowToConstrain htc,
351  HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
352  unsigned int c_d0, unsigned int a_d0, unsigned int t0)
353  : Test(b+"::"+Model::name()+"::"+str(htc)+"::"+
354  str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
355  str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
356  htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
358  virtual bool run(void) {
359  Model* m = new Model(htb1,htb2,htb3,htc);
362  o.c_d = c_d;
363  o.a_d = a_d;
364  o.threads = t;
365  o.stop = &f;
366  Engine<Model> best(m,o);
367  delete m;
368  Model* b = NULL;
369  while (true) {
370  Model* s = best.next();
371  if (s != NULL) {
372  delete b; b=s;
373  }
374  if ((s == NULL) && !best.stopped())
375  break;
376  f.limit(f.limit()+2);
377  }
378  bool ok = (b == NULL) || b->best();
379  delete b;
380  return ok;
381  }
382  };
383 
385  class BranchTypes {
386  private:
388  static const HowToBranch htbs[3];
390  int i;
391  public:
393  BranchTypes(void) : i(0) {}
395  bool operator()(void) const {
396  return i<3;
397  }
399  void operator++(void) {
400  i++;
401  }
403  HowToBranch htb(void) const {
404  return htbs[i];
405  }
406  };
407 
408  const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
409 
412  private:
414  static const HowToConstrain htcs[4];
416  int i;
417  public:
419  ConstrainTypes(void) : i(0) {}
421  bool operator()(void) const {
422  return i<4;
423  }
425  void operator++(void) {
426  i++;
427  }
429  HowToConstrain htc(void) const {
430  return htcs[i];
431  }
432  };
433 
434  const HowToConstrain ConstrainTypes::htcs[4] =
436 
437 
439  class Create {
440  public:
442  Create(void) {
443  // Depth-first search
444  for (unsigned int t = 1; t<=4; t++)
445  for (unsigned int c_d = 1; c_d<10; c_d++)
446  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
447  for (BranchTypes htb1; htb1(); ++htb1)
448  for (BranchTypes htb2; htb2(); ++htb2)
449  for (BranchTypes htb3; htb3(); ++htb3)
450  (void) new DFS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb(),
451  c_d, a_d, t);
453  c_d, a_d, t);
455  c_d, a_d, t);
456  }
457 
458  // Best solution search
459  for (unsigned int t = 1; t<=4; t++)
460  for (unsigned int c_d = 1; c_d<10; c_d++)
461  for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
462  for (ConstrainTypes htc; htc(); ++htc)
463  for (BranchTypes htb1; htb1(); ++htb1)
464  for (BranchTypes htb2; htb2(); ++htb2)
465  for (BranchTypes htb3; htb3(); ++htb3) {
466  (void) new Best<HasSolutions,BAB>
467  ("BAB",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
468  c_d,a_d,t);
469  (void) new Best<HasSolutions,Restart>
470  ("Restart",htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
471  c_d,a_d,t);
472  }
473  (void) new Best<FailImmediate,BAB>
475  (void) new Best<HasSolutions,BAB>
477  }
478 
479  }
480  };
481 
483  }
484 
485 }
486 
487 // STATISTICS: test-search