this repo has no description
dekker.one
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 * 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
43namespace Test {
44
45 /// Tests for search using no-goods
46 namespace NoGoods {
47
48 using namespace Gecode;
49
50 /// A dummy function for branching
51 void dummy(Space&) {
52 }
53
54 /// Example for testing integer no-goods
55 class Queens : public Space {
56 public:
57 /// Number of queens (must be even)
58 const static int n = 18;
59 /// Position of queens on boards
60 IntVarArray q;
61 /// The actual problem
62 Queens(IntValBranch ivb, bool assign, bool null)
63 : q(*this,n,0,n-1) {
64 distinct(*this, IntArgs::create(n,0,1), q, IPL_VAL);
65 distinct(*this, IntArgs::create(n,0,-1), q, IPL_VAL);
66 distinct(*this, q, IPL_VAL);
67 if (assign) {
68 IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
69 }
70 {
71 IntVarArgs q1(n/2), q2(n/2);
72 for (int i=0; i<n/2; i++) {
73 q1[i] = q[i]; q2[i] = q[n/2 + i];
74 }
75 branch(*this, q1, INT_VAR_NONE(), ivb);
76 if (null)
77 branch(*this, &dummy);
78 branch(*this, q2, INT_VAR_NONE(), ivb);
79 }
80 if (assign) {
81 IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
82 }
83 }
84 /// Constructor for cloning \a s
85 Queens(Queens& s) : Space(s) {
86 q.update(*this, s.q);
87 }
88 /// Perform copying during cloning
89 virtual Space* copy(void) {
90 return new Queens(*this);
91 }
92 /// Check whether two solutions are the same
93 bool same(const Queens& s) const {
94 for (int i=0; i<q.size(); i++)
95 if (q[i].val() != s.q[i].val())
96 return false;
97 return true;
98 }
99 /// Return increment for node stop
100 static unsigned int nodeinc(void) {
101 return 500;
102 }
103 /// Return name
104 static std::string name(void) {
105 return "Queens";
106 }
107 /// Return name for branching
108 static std::string val(IntValBranch ivb) {
109 switch (ivb.select()) {
110 case IntValBranch::SEL_MIN: return "INT_VAL_MIN";
111 case IntValBranch::SEL_MAX: return "INT_VAL_MAX";
112 case IntValBranch::SEL_SPLIT_MIN: return "INT_VAL_SPLIT_MIN";
113 case IntValBranch::SEL_SPLIT_MAX: return "INT_VAL_SPLIT_MAX";
114 case IntValBranch::SEL_VALUES_MIN: return "INT_VALUES_MIN";
115 case IntValBranch::SEL_VALUES_MAX: return "INT_VALUES_MAX";
116 default: GECODE_NEVER;
117 }
118 return "";
119 }
120 };
121
122#ifdef GECODE_HAS_SET_VARS
123 /// Example for testing set no-goods
124 class Hamming : public Space {
125 private:
126 /// Number of symbols (must be even)
127 static const int size = 16;
128 /// Minimal Hamming-distance
129 static const int distance = 4;
130 /// Number of bits
131 static const int bits = 8;
132 /// The hamming code
133 SetVarArray x;
134 public:
135 /// Actual model
136 Hamming(SetValBranch svb, bool assign, bool null) :
137 x(*this,size,IntSet::empty,1,bits) {
138 SetVarArgs cx(x.size());
139 for (int i=x.size(); i--;)
140 cx[i] = expr(*this, -x[i]);
141
142 for (int i=0; i<x.size(); i++)
143 for (int j=i+1; j<x.size(); j++)
144 rel(*this,
145 cardinality(x[j] & cx[i]) +
146 cardinality(x[i] & cx[j]) >= distance);
147
148 if (assign) {
149 IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
150 }
151 {
152 SetVarArgs x1(size/2), x2(size/2);
153 for (int i=0; i<size/2; i++) {
154 x1[i] = x[i]; x2[i] = x[size/2 + i];
155 }
156 branch(*this, x1, SET_VAR_NONE(), svb);
157 if (null)
158 branch(*this, &dummy);
159 branch(*this, x2, SET_VAR_NONE(), svb);
160 }
161 if (assign) {
162 IntVar x(*this,0,1); Gecode::assign(*this, x, INT_ASSIGN_MIN());
163 }
164 }
165 /// Constructor for copying \a s
166 Hamming(Hamming& s) : Space(s) {
167 x.update(*this, s.x);
168 }
169 /// Copy during cloning
170 virtual Space* copy(void) {
171 return new Hamming(*this);
172 }
173 /// Check whether two solutions are the same
174 bool same(const Hamming& s) const {
175 for (int i=0; i<x.size(); i++) {
176 SetVarGlbRanges a(x[i]), b(s.x[i]);
177 if (!Iter::Ranges::equal(a,b))
178 return false;
179 }
180 return true;
181 }
182 /// Return increment for node stop
183 static unsigned int nodeinc(void) {
184 return 35;
185 }
186 /// Return name
187 static std::string name(void) {
188 return "Hamming";
189 }
190 /// Return name for branching
191 static std::string val(SetValBranch svb) {
192 switch (svb.select()) {
193 case SetValBranch::SEL_MIN_INC: return "SET_VAL_MIN_INC";
194 case SetValBranch::SEL_MAX_INC: return "SET_VAL_MAX_INC";
195 case SetValBranch::SEL_MIN_EXC: return "SET_VAL_MIN_EXC";
196 case SetValBranch::SEL_MAX_EXC: return "SET_VAL_MAX_EXC";
197 default: GECODE_NEVER;
198 }
199 return "";
200 }
201 };
202#endif
203
204 /// %Base class for no-good tests
205 template<class Model, class ValBranch>
206 class NoGoods : public Base {
207 protected:
208 /// How to branch
209 ValBranch vb;
210 /// Number of threads to use
211 unsigned int t;
212 /// Whether to also assign some variables
213 bool a;
214 /// Whether to also create branchers without no-good literals
215 bool n;
216 public:
217 /// Map unsigned integer to string
218 static std::string str(unsigned int i) {
219 std::stringstream s;
220 s << i;
221 return s.str();
222 }
223 /// Initialize test
224 NoGoods(ValBranch vb0, unsigned int t0, bool a0, bool n0)
225 : Base("NoGoods::"+Model::name()+"::"+Model::val(vb0)+"::"+str(t0)+
226 "::"+(a0 ? "+" : "-")+"::"+(n0 ? "+" : "-")),
227 vb(vb0), t(t0), a(a0), n(n0) {}
228 /// Run test
229 virtual bool run(void) {
230 Model* m = new Model(vb,a,n);
231 // Solution without no-goods
232 Model* s_plain = dfs(m);
233 // Stop and re-start for a while to collect no-goods
234 {
235 Search::NodeStop ns(Model::nodeinc());
236 Search::Options o;
237 o.stop = &ns;
238 o.threads = t;
239 o.nogoods_limit = 256U;
240 Search::Engine* e = Search::dfsengine(m,o);
241 while (true) {
242 Model* s = static_cast<Model*>(e->next());
243 delete s;
244 if (!e->stopped())
245 break;
246 // Add no-goods
247 e->nogoods().post(*m);
248 ns.limit(ns.limit()+Model::nodeinc());
249 }
250 delete e;
251 }
252 // Compare whether the a or the same solution is found with no-goods
253 Model* s_nogoods = dfs(m);
254
255 bool ok = ((s_nogoods != nullptr) &&
256 ((t != 1) || s_plain->same(*s_nogoods)));
257
258 delete m;
259 delete s_nogoods;
260 delete s_plain;
261
262 return ok;
263 }
264 };
265
266
267 /// Help class to create and register tests
268 class Create {
269 public:
270 /// Perform creation and registration
271 Create(void) {
272 bool a = false;
273 do {
274 bool n = false;
275 do {
276 for (unsigned int t = 1; t<=4; t++) {
277 (void) new NoGoods<Queens,IntValBranch>(INT_VAL_MIN(),t,a,n);
278 (void) new NoGoods<Queens,IntValBranch>(INT_VAL_MAX(),t,a,n);
279 (void) new NoGoods<Queens,IntValBranch>(INT_VAL_SPLIT_MIN(),t,a,n);
280 (void) new NoGoods<Queens,IntValBranch>(INT_VAL_SPLIT_MAX(),t,a,n);
281 (void) new NoGoods<Queens,IntValBranch>(INT_VALUES_MIN(),t,a,n);
282 (void) new NoGoods<Queens,IntValBranch>(INT_VALUES_MAX(),t,a,n);
283#ifdef GECODE_HAS_SET_VARS
284 (void) new NoGoods<Hamming,SetValBranch>(SET_VAL_MIN_INC(),t,a,n);
285 (void) new NoGoods<Hamming,SetValBranch>(SET_VAL_MIN_EXC(),t,a,n);
286 (void) new NoGoods<Hamming,SetValBranch>(SET_VAL_MAX_INC(),t,a,n);
287 (void) new NoGoods<Hamming,SetValBranch>(SET_VAL_MAX_EXC(),t,a,n);
288#endif
289 }
290 n = !n;
291 } while (n);
292 a = !a;
293 } while (a);
294 }
295 };
296
297 Create c;
298 }
299
300}
301
302// STATISTICS: test-search