Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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
Which values to select for branching first.
Definition: set.hh:1382
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:72
bool same(const Hamming &s) const
Check whether two solutions are the same.
Definition: nogoods.cpp:178
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:215
unsigned int t
Number of threads to use.
Definition: nogoods.cpp:215
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
Select all values starting from smallest.
Definition: int.hh:3994
Help class to create and register tests.
Definition: nogoods.cpp:271
unsigned long int limit(void) const
Return current limit.
Definition: stop.hpp:69
bool a
Whether to also assign some variables.
Definition: nogoods.cpp:217
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:91
static std::string val(SetValBranch svb)
Return name for branching.
Definition: nogoods.cpp:195
Stop-object based on number of nodes
Definition: search.hh:284
NoGoods(ValBranch vb0, unsigned int t0, bool a0, bool n0)
Initialize test.
Definition: nogoods.cpp:228
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition: nogoods.cpp:222
ValBranch vb
How to branch.
Definition: nogoods.cpp:213
Select values greater than mean of smallest and largest value.
Definition: int.hh:3990
void dummy(Space &home)
A dummy function for branching.
Definition: nogoods.cpp:55
Which values to select for branching first.
Definition: int.hh:3981
Search engine options
Definition: search.hh:204
Value propagation or consistency (naive)
Definition: int.hh:938
Select all values starting from largest.
Definition: int.hh:3995
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
Definition: val.hpp:59
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Select select(void) const
Return selection strategy.
Definition: val.hpp:53
Select values not greater than mean of smallest and largest value.
Definition: int.hh:3989
Integer variable array.
Definition: int.hh:741
Select select(void) const
Return selection strategy.
Definition: val.hpp:57
Hamming(bool share, Hamming &s)
Constructor for copying s.
Definition: nogoods.cpp:170
Example for testing set no-goods.
Definition: nogoods.cpp:128
virtual bool run(void)
Run test.
Definition: nogoods.cpp:233
Include smallest element.
Definition: set.hh:1386
Example for testing integer no-goods.
Definition: nogoods.cpp:59
Computation spaces.
Definition: core.hpp:1362
static std::string val(IntValBranch ivb)
Return name for branching.
Definition: nogoods.cpp:112
virtual Space * copy(bool share)
Copy during cloning.
Definition: nogoods.cpp:174
Hamming(SetValBranch svb, bool assign, bool null)
Actual model.
Definition: nogoods.cpp:140
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
virtual void post(Space &home) const
Post no-goods.
Definition: core.cpp:82
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
static std::string name(void)
Return name.
Definition: nogoods.cpp:108
Create(void)
Perform creation and registration.
Definition: nogoods.cpp:274
Include largest element.
Definition: set.hh:1390
double threads
Number of threads to use.
Definition: search.hh:209
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:207
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
Select smallest value.
Definition: int.hh:3985
unsigned int size(I &i)
Size of all ranges of range iterator i.
IntValBranch INT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition: val.hpp:93
Base class for all tests to be run
Definition: test.hh:107
SetValBranch SET_VAL_MAX_EXC(void)
Exclude largest element.
Definition: val.hpp:84
Iterator for the greatest lower bound ranges of a set variable.
Definition: set.hh:272
Queens(bool share, Queens &s)
Constructor for cloning s.
Definition: nogoods.cpp:89
Exclude largest element.
Definition: set.hh:1391
SetValBranch SET_VAL_MAX_INC(void)
Include largest element.
Definition: val.hpp:79
Queens(IntValBranch ivb, bool assign, bool null)
The actual problem.
Definition: nogoods.cpp:66
Select largest value.
Definition: int.hh:3987
Integer sets.
Definition: int.hh:171
IntVarArray q
Position of queens on boards.
Definition: nogoods.cpp:64
Passing integer variables.
Definition: int.hh:636
SetValBranch SET_VAL_MIN_EXC(void)
Exclude smallest element.
Definition: val.hpp:64
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:815
bool stopped(void) const
Check whether engine has been stopped.
Definition: dfs.hpp:64
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:78
General test support.
Definition: afc.cpp:43
Exclude smallest element.
Definition: set.hh:1387
Passing set variables.
Definition: set.hh:490
Value branching information.
Definition: branch-val.hpp:44
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:120
BrancherHandle assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
No-goods recorded from restarts.
Definition: core.hpp:1240
IntValBranch INT_VALUES_MAX(void)
Try all values starting from largest.
Definition: val.hpp:125
Integer variables.
Definition: int.hh:350
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
static unsigned int nodeinc(void)
Return increment for node stop.
Definition: nogoods.cpp:187
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
static unsigned int nodeinc(void)
Return increment for node stop.
Definition: nogoods.cpp:104
Set variable array
Definition: set.hh:571
Stop * stop
Stop object for stopping search.
Definition: search.hh:217
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:88
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
BrancherHandle 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
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:70
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
bool n
Whether to also create branchers without no-good literals.
Definition: nogoods.cpp:219
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:494
static std::string name(void)
Return name.
Definition: nogoods.cpp:191
bool same(const Queens &s) const
Check whether two solutions are the same.
Definition: nogoods.cpp:97
Example: Generating Hamming codes
Definition: hamming.cpp:90
virtual Space * copy(bool share)
Perform copying during cloning.
Definition: nogoods.cpp:93