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 * Copyright:
7 * Christian Schulte, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include "test/int.hh"
35
36#include <gecode/minimodel.hh>
37
38namespace Test { namespace Int {
39
40 /// %Tests for linear constraints
41 namespace Linear {
42
43 /// Check whether \a a has only one coefficients
44 bool one(const Gecode::IntArgs& a) {
45 for (int i=a.size(); i--; )
46 if (a[i] != 1)
47 return false;
48 return true;
49 }
50
51 /**
52 * \defgroup TaskTestIntLinear Linear constraints
53 * \ingroup TaskTestInt
54 */
55 //@{
56 /// %Test linear relation over integer variables
57 class IntInt : public Test {
58 protected:
59 /// Coefficients
60 Gecode::IntArgs a;
61 /// Integer relation type to propagate
62 Gecode::IntRelType irt;
63 /// Result
64 int c;
65 public:
66 /// Create and register test
67 IntInt(const std::string& s, const Gecode::IntSet& d,
68 const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
69 int c0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
70 : Test("Linear::Int::Int::"+
71 str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(c0)+"::"
72 +str(a0.size()),
73 a0.size(),d,ipl != Gecode::IPL_DOM,ipl),
74 a(a0), irt(irt0), c(c0) {
75 testfix=false;
76 }
77 /// %Test whether \a x is solution
78 virtual bool solution(const Assignment& x) const {
79 double e = 0.0;
80 for (int i=0; i<x.size(); i++)
81 e += a[i]*x[i];
82 return cmp(e, irt, static_cast<double>(c));
83 }
84 /// Post constraint on \a x
85 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
86 if (one(a))
87 Gecode::linear(home, x, irt, c, ipl);
88 else
89 Gecode::linear(home, a, x, irt, c, ipl);
90 }
91 /// Post reified constraint on \a x for \a r
92 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
93 Gecode::Reify r) {
94 if (one(a))
95 Gecode::linear(home, x, irt, c, r, ipl);
96 else
97 Gecode::linear(home, a, x, irt, c, r, ipl);
98 }
99 };
100
101 /// %Test linear relation over integer variables
102 class IntVar : public Test {
103 protected:
104 /// Coefficients
105 Gecode::IntArgs a;
106 /// Integer relation type to propagate
107 Gecode::IntRelType irt;
108 public:
109 /// Create and register test
110 IntVar(const std::string& s, const Gecode::IntSet& d,
111 const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
112 Gecode::IntPropLevel ipl=Gecode::IPL_BND)
113 : Test("Linear::Int::Var::"+
114 str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(a0.size()),
115 a0.size()+1,d,ipl != Gecode::IPL_DOM,ipl),
116 a(a0), irt(irt0) {
117 testfix=false;
118 }
119 /// %Test whether \a x is solution
120 virtual bool solution(const Assignment& x) const {
121 double e = 0.0;
122 for (int i=0; i<a.size(); i++)
123 e += a[i]*x[i];
124 return cmp(e, irt, static_cast<double>(x[a.size()]));
125 }
126 /// Post constraint on \a x
127 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
128 int n = a.size();
129 Gecode::IntVarArgs y(n);
130 for (int i=n; i--; )
131 y[i] = x[i];
132 if (one(a))
133 Gecode::linear(home, y, irt, x[n], ipl);
134 else
135 Gecode::linear(home, a, y, irt, x[n], ipl);
136 }
137 /// Post reified constraint on \a x for \a r
138 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
139 Gecode::Reify r) {
140 int n = a.size();
141 Gecode::IntVarArgs y(n);
142 for (int i=n; i--; )
143 y[i] = x[i];
144 if (one(a))
145 Gecode::linear(home, y, irt, x[n], r, ipl);
146 else
147 Gecode::linear(home, a, y, irt, x[n], r, ipl);
148 }
149 };
150
151 /// %Test linear relation over Boolean variables equal to constant
152 class BoolInt : public Test {
153 protected:
154 /// Coefficients
155 Gecode::IntArgs a;
156 /// Integer relation type to propagate
157 Gecode::IntRelType irt;
158 /// Righthand-side constant
159 int c;
160 public:
161 /// Create and register test
162 BoolInt(const std::string& s, const Gecode::IntArgs& a0,
163 Gecode::IntRelType irt0, int c0)
164 : Test("Linear::Bool::Int::"+
165 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
166 a0.size(),0,1,true,Gecode::IPL_DEF),
167 a(a0), irt(irt0), c(c0) {
168 testfix=false;
169 }
170 /// %Test whether \a x is solution
171 virtual bool solution(const Assignment& x) const {
172 double e = 0.0;
173 for (int i=0; i<x.size(); i++)
174 e += a[i]*x[i];
175 return cmp(e, irt, static_cast<double>(c));
176 }
177 /// Post constraint on \a x
178 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
179 Gecode::BoolVarArgs y(x.size());
180 for (int i=x.size(); i--; )
181 y[i]=Gecode::channel(home,x[i]);
182 if (one(a))
183 Gecode::linear(home, y, irt, c, Gecode::IPL_DEF);
184 else
185 Gecode::linear(home, a, y, irt, c, Gecode::IPL_DEF);
186 }
187 /// Post reified constraint on \a x for \a r
188 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
189 Gecode::Reify r) {
190 Gecode::BoolVarArgs y(x.size());
191 for (int i=x.size(); i--; )
192 y[i]=Gecode::channel(home,x[i]);
193 if (one(a))
194 Gecode::linear(home, y, irt, c, r, Gecode::IPL_DEF);
195 else
196 Gecode::linear(home, a, y, irt, c, r, Gecode::IPL_DEF);
197 }
198 };
199
200 /// %Test linear relation over Boolean variables equal to integer variable
201 class BoolVar : public Test {
202 protected:
203 /// Coefficients
204 Gecode::IntArgs a;
205 /// Integer relation type to propagate
206 Gecode::IntRelType irt;
207 public:
208 /// Create and register test
209 BoolVar(const std::string& s,
210 int min, int max, const Gecode::IntArgs& a0,
211 Gecode::IntRelType irt0)
212 : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
213 min,max,true),
214 a(a0), irt(irt0) {
215 testfix=false;
216 }
217 /// %Test whether \a x is solution
218 virtual bool solution(const Assignment& x) const {
219 int n=x.size()-1;
220 for (int i=0; i<n; i++)
221 if ((x[i] < 0) || (x[i] > 1))
222 return false;
223 double e = 0.0;
224 for (int i=0; i<n; i++)
225 e += a[i]*x[i];
226 return cmp(e, irt, static_cast<double>(x[n]));
227 }
228 /// %Test whether \a x is to be ignored
229 virtual bool ignore(const Assignment& x) const {
230 for (int i=x.size()-1; i--; )
231 if ((x[i] < 0) || (x[i] > 1))
232 return true;
233 return false;
234 }
235 /// Post constraint on \a x
236 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
237 int n=x.size()-1;
238 Gecode::BoolVarArgs y(n);
239 for (int i=n; i--; )
240 y[i]=Gecode::channel(home,x[i]);
241 if (one(a))
242 Gecode::linear(home, y, irt, x[n]);
243 else
244 Gecode::linear(home, a, y, irt, x[n]);
245 }
246 /// Post reified constraint on \a x for \a r
247 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
248 Gecode::Reify r) {
249 int n=x.size()-1;
250 Gecode::BoolVarArgs y(n);
251 for (int i=n; i--; )
252 y[i]=Gecode::channel(home,x[i]);
253 if (one(a))
254 Gecode::linear(home, y, irt, x[n], r);
255 else
256 Gecode::linear(home, a, y, irt, x[n], r);
257 }
258 };
259
260 /// Help class to create and register tests
261 class Create {
262 public:
263 /// Perform creation and registration
264 Create(void) {
265 using namespace Gecode;
266 {
267 IntSet d1(-2,2);
268 const int dv2[] = {-4,-1,0,1,4};
269 IntSet d2(dv2,5);
270
271 const int dv3[] = {0,1500000000};
272 IntSet d3(dv3,2);
273
274 IntArgs a1({0});
275
276 for (IntRelTypes irts; irts(); ++irts) {
277 (void) new IntInt("11",d1,a1,irts.irt(),0);
278 (void) new IntVar("11",d1,a1,irts.irt());
279 (void) new IntInt("21",d2,a1,irts.irt(),0);
280 (void) new IntVar("21",d2,a1,irts.irt());
281 (void) new IntInt("31",d3,a1,irts.irt(),150000000);
282 }
283 (void) new IntInt("11",d1,a1,IRT_EQ,0,IPL_DOM);
284 (void) new IntVar("11",d1,a1,IRT_EQ,IPL_DOM);
285 (void) new IntInt("21",d2,a1,IRT_EQ,0,IPL_DOM);
286 (void) new IntVar("21",d2,a1,IRT_EQ,IPL_DOM);
287
288 const int av2[5] = {1,1,1,1,1};
289 const int av3[5] = {1,-1,-1,1,-1};
290 const int av4[5] = {2,3,5,7,11};
291 const int av5[5] = {-2,3,-5,7,-11};
292
293
294 for (int i=1; i<=5; i++) {
295 IntArgs a2(i, av2);
296 IntArgs a3(i, av3);
297 IntArgs a4(i, av4);
298 IntArgs a5(i, av5);
299 for (IntRelTypes irts; irts(); ++irts) {
300 (void) new IntInt("12",d1,a2,irts.irt(),0);
301 (void) new IntInt("13",d1,a3,irts.irt(),0);
302 (void) new IntInt("14",d1,a4,irts.irt(),0);
303 (void) new IntInt("15",d1,a5,irts.irt(),0);
304 (void) new IntInt("22",d2,a2,irts.irt(),0);
305 (void) new IntInt("23",d2,a3,irts.irt(),0);
306 (void) new IntInt("24",d2,a4,irts.irt(),0);
307 (void) new IntInt("25",d2,a5,irts.irt(),0);
308 (void) new IntInt("32",d3,a2,irts.irt(),1500000000);
309 if (i < 5) {
310 (void) new IntVar("12",d1,a2,irts.irt());
311 (void) new IntVar("13",d1,a3,irts.irt());
312 (void) new IntVar("14",d1,a4,irts.irt());
313 (void) new IntVar("15",d1,a5,irts.irt());
314 (void) new IntVar("22",d2,a2,irts.irt());
315 (void) new IntVar("23",d2,a3,irts.irt());
316 (void) new IntVar("24",d2,a4,irts.irt());
317 (void) new IntVar("25",d2,a5,irts.irt());
318 }
319 }
320 (void) new IntInt("12",d1,a2,IRT_EQ,0,IPL_DOM);
321 (void) new IntInt("13",d1,a3,IRT_EQ,0,IPL_DOM);
322 (void) new IntInt("14",d1,a4,IRT_EQ,0,IPL_DOM);
323 (void) new IntInt("15",d1,a5,IRT_EQ,0,IPL_DOM);
324 (void) new IntInt("22",d2,a2,IRT_EQ,0,IPL_DOM);
325 (void) new IntInt("23",d2,a3,IRT_EQ,0,IPL_DOM);
326 (void) new IntInt("24",d2,a4,IRT_EQ,0,IPL_DOM);
327 (void) new IntInt("25",d2,a5,IRT_EQ,0,IPL_DOM);
328 if (i < 4) {
329 (void) new IntVar("12",d1,a2,IRT_EQ,IPL_DOM);
330 (void) new IntVar("13",d1,a3,IRT_EQ,IPL_DOM);
331 (void) new IntVar("14",d1,a4,IRT_EQ,IPL_DOM);
332 (void) new IntVar("15",d1,a5,IRT_EQ,IPL_DOM);
333 }
334 }
335 }
336 {
337 const int av1[10] = {
338 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
339 };
340 const int av2[10] = {
341 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
342 };
343
344 for (int i=1; i<=10; i += 3) {
345 IntArgs a1(i, av1);
346 IntArgs a2(i, av2);
347 for (int c=0; c<=6; c++)
348 for (IntRelTypes irts; irts(); ++irts) {
349 (void) new BoolInt("1",a1,irts.irt(),c);
350 (void) new BoolInt("2",a2,irts.irt(),-c);
351 }
352 }
353
354 IntArgs a3({1,2,3,4,5});
355 IntArgs a4({-1,-2,-3,-4,-5});
356 IntArgs a5({-1,-2,1,2,4});
357
358 for (IntRelTypes irts; irts(); ++irts) {
359 for (int c=0; c<=16; c++) {
360 (void) new BoolInt("3",a3,irts.irt(),c);
361 (void) new BoolInt("4",a4,irts.irt(),-c);
362 (void) new BoolInt("5",a5,irts.irt(),c);
363 (void) new BoolInt("6",a5,irts.irt(),-c);
364 }
365 }
366
367 for (int i=1; i<=5; i += 2) {
368 IntArgs a1(i, av1);
369 IntArgs a2(i, av2);
370 for (IntRelTypes irts; irts(); ++irts) {
371 (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
372 (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
373 }
374 }
375
376 IntArgs a6({1,2,3,4});
377 IntArgs a7({-1,-2,-3,-4});
378 IntArgs a8({-1,-2,1,2});
379 IntArgs a9({-1,-2,1,2,-3,3});
380
381 for (IntRelTypes irts; irts(); ++irts) {
382 (void) new BoolVar("6",0,10,a6,irts.irt());
383 (void) new BoolVar("7",-10,0,a7,irts.irt());
384 (void) new BoolVar("8",-3,3,a8,irts.irt());
385 (void) new BoolVar("9",-3,3,a9,irts.irt());
386 }
387
388 }
389 }
390 };
391
392 Create c;
393 //@}
394
395 }
396}}
397
398// STATISTICS: test-int