Generated on Sat Nov 9 2013 19:18:31 for Gecode by doxygen 1.8.4
nogoods.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  * Contributing authors:
7  * Guido Tack <tack@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2013
11  * Guido Tack, 2004
12  *
13  * Last modified:
14  * $Date: 2013-07-09 12:19:11 +0200 (Tue, 09 Jul 2013) $ by $Author: schulte $
15  * $Revision: 13831 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/minimodel.hh>
43 #include <gecode/search.hh>
44 
45 #include "test/test.hh"
46 
47 namespace Test {
48 
50  namespace NoGoods {
51 
52  using namespace Gecode;
53 
55  void dummy(Space& home) {
56  }
57 
59  class Queens : public Space {
60  public:
62  const static int n = 18;
66  Queens(IntValBranch ivb, bool assign, bool null)
67  : q(*this,n,0,n-1) {
68  distinct(*this, IntArgs::create(n,0,1), q, ICL_VAL);
69  distinct(*this, IntArgs::create(n,0,-1), q, ICL_VAL);
70  distinct(*this, q, ICL_VAL);
71  if (assign) {
72  IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
73  }
74  {
75  IntVarArgs q1(n/2), q2(n/2);
76  for (int i=0; i<n/2; i++) {
77  q1[i] = q[i]; q2[i] = q[n/2 + i];
78  }
79  branch(*this, q1, INT_VAR_NONE(), ivb);
80  if (null)
81  branch(*this, &dummy);
82  branch(*this, q2, INT_VAR_NONE(), ivb);
83  }
84  if (assign) {
85  IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
86  }
87  }
89  Queens(bool share, Queens& s) : Space(share,s) {
90  q.update(*this, share, s.q);
91  }
93  virtual Space* copy(bool share) {
94  return new Queens(share,*this);
95  }
97  bool same(const Queens& s) const {
98  for (int i=0; i<q.size(); i++)
99  if (q[i].val() != s.q[i].val())
100  return false;
101  return true;
102  }
104  static unsigned int nodeinc(void) {
105  return 500;
106  }
108  static std::string name(void) {
109  return "Queens";
110  }
112  static std::string val(IntValBranch ivb) {
113  switch (ivb.select()) {
114  case IntValBranch::SEL_MIN: return "INT_VAL_MIN";
115  case IntValBranch::SEL_MAX: return "INT_VAL_MAX";
116  case IntValBranch::SEL_SPLIT_MIN: return "INT_VAL_SPLIT_MIN";
117  case IntValBranch::SEL_SPLIT_MAX: return "INT_VAL_SPLIT_MAX";
118  case IntValBranch::SEL_VALUES_MIN: return "INT_VALUES_MIN";
119  case IntValBranch::SEL_VALUES_MAX: return "INT_VALUES_MAX";
120  default: GECODE_NEVER;
121  }
122  return "";
123  }
124  };
125 
126 #ifdef GECODE_HAS_SET_VARS
127  class Hamming : public Space {
129  private:
131  static const int size = 16;
133  static const int distance = 4;
135  static const int bits = 8;
137  SetVarArray x;
138  public:
140  Hamming(SetValBranch svb, bool assign, bool null) :
141  x(*this,size,IntSet::empty,1,bits) {
142  SetVarArgs cx(x.size());
143  for (int i=x.size(); i--;)
144  cx[i] = expr(*this, -x[i]);
145 
146  for (int i=0; i<x.size(); i++)
147  for (int j=i+1; j<x.size(); j++)
148  rel(*this,
149  cardinality(x[j] & cx[i]) +
150  cardinality(x[i] & cx[j]) >= distance);
151 
152  if (assign) {
153  IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
154  }
155  {
156  SetVarArgs x1(size/2), x2(size/2);
157  for (int i=0; i<size/2; i++) {
158  x1[i] = x[i]; x2[i] = x[size/2 + i];
159  }
160  branch(*this, x1, SET_VAR_NONE(), svb);
161  if (null)
162  branch(*this, &dummy);
163  branch(*this, x2, SET_VAR_NONE(), svb);
164  }
165  if (assign) {
166  IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
167  }
168  }
170  Hamming(bool share, Hamming& s) : Space(share,s) {
171  x.update(*this, share, s.x);
172  }
174  virtual Space* copy(bool share) {
175  return new Hamming(share,*this);
176  }
178  bool same(const Hamming& s) const {
179  for (int i=0; i<x.size(); i++) {
180  SetVarGlbRanges a(x[i]), b(s.x[i]);
181  if (!Iter::Ranges::equal(a,b))
182  return false;
183  }
184  return true;
185  }
187  static unsigned int nodeinc(void) {
188  return 35;
189  }
191  static std::string name(void) {
192  return "Hamming";
193  }
195  static std::string val(SetValBranch svb) {
196  switch (svb.select()) {
197  case SetValBranch::SEL_MIN_INC: return "SET_VAL_MIN_INC";
198  case SetValBranch::SEL_MAX_INC: return "SET_VAL_MAX_INC";
199  case SetValBranch::SEL_MIN_EXC: return "SET_VAL_MIN_EXC";
200  case SetValBranch::SEL_MAX_EXC: return "SET_VAL_MAX_EXC";
201  default: GECODE_NEVER;
202  }
203  return "";
204  }
205  };
206 #endif
207 
209  template<class Model, class ValBranch>
210  class NoGoods : public Base {
211  protected:
215  unsigned int t;
217  bool a;
219  bool n;
220  public:
222  static std::string str(unsigned int i) {
223  std::stringstream s;
224  s << i;
225  return s.str();
226  }
228  NoGoods(ValBranch vb0, unsigned int t0, bool a0, bool n0)
229  : Base("NoGoods::"+Model::name()+"::"+Model::val(vb0)+"::"+str(t0)+
230  "::"+(a0 ? "+" : "-")+"::"+(n0 ? "+" : "-")),
231  vb(vb0), t(t0), a(a0), n(n0) {}
233  virtual bool run(void) {
234  Model* m = new Model(vb,a,n);
235  // Solution without no-goods
236  Model* s_plain = dfs(m);
237  // Stop and re-start for a while to collect no-goods
238  {
239  Search::NodeStop ns(Model::nodeinc());
240  Search::Options o;
241  o.stop = &ns;
242  o.threads = t;
243  o.nogoods_limit = 256U;
244  DFS<Model> e(m,o);
245  while (true) {
246  Model* s = e.next();
247  delete s;
248  if (!e.stopped())
249  break;
250  // Add no-goods
251  e.nogoods().post(*m);
252  ns.limit(ns.limit()+Model::nodeinc());
253  }
254  }
255  // Compare whether the a or the same solution is found with no-goods
256  Model* s_nogoods = dfs(m);
257 
258  bool ok = ((s_nogoods != NULL) &&
259  ((t != 1) || s_plain->same(*s_nogoods)));
260 
261  delete m;
262  delete s_nogoods;
263  delete s_plain;
264 
265  return ok;
266  }
267  };
268 
269 
271  class Create {
272  public:
274  Create(void) {
275  bool a = false;
276  do {
277  bool n = false;
278  do {
279  for (unsigned int t = 1; t<=4; t++) {
286 #ifdef GECODE_HAS_SET_VARS
291 #endif
292  }
293  n = !n;
294  } while (n);
295  a = !a;
296  } while (a);
297  }
298  };
299 
301  }
302 
303 }
304 
305 // STATISTICS: test-search