Generated on for Gecode by doxygen 1.17.0
linear.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.dev>
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.dev
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
41 namespace Linear {
42
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
56
57 class IntInt : public Test {
58 protected:
64 int c;
65 public:
67 IntInt(TestTags tags, const std::string& s, const Gecode::IntSet& d,
68 const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
70 : Test(tags,"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
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
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
92 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
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
102 class IntVar : public Test {
103 protected:
108 public:
110 IntVar(const std::string& s, const Gecode::IntSet& d,
111 const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
113 : Test(TestTags::sweep(),"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
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
127 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
128 int n = a.size();
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
138 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
140 int n = a.size();
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
152 class BoolInt : public Test {
153 protected:
159 int c;
160 public:
162 BoolInt(const std::string& s, const Gecode::IntArgs& a0,
163 Gecode::IntRelType irt0, int c0)
164 : Test(irt0 == Gecode::IRT_LQ
165 ? TestTags::check()
166 : TestTags(TestTags::sweep()),"Linear::Bool::Int::"+
167 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
168 a0.size(),0,1,true,Gecode::IPL_DEF),
169 a(a0), irt(irt0), c(c0) {
170 testfix=false;
171 }
172
173 virtual bool solution(const Assignment& x) const {
174 double e = 0.0;
175 for (int i=0; i<x.size(); i++)
176 e += a[i]*x[i];
177 return cmp(e, irt, static_cast<double>(c));
178 }
179
180 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
182 for (int i=x.size(); i--; )
183 y[i]=Gecode::channel(home,x[i]);
184 if (one(a))
186 else
187 Gecode::linear(home, a, y, irt, c, Gecode::IPL_DEF);
188 }
189
190 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
193 for (int i=x.size(); i--; )
194 y[i]=Gecode::channel(home,x[i]);
195 if (one(a))
196 Gecode::linear(home, y, irt, c, r, Gecode::IPL_DEF);
197 else
198 Gecode::linear(home, a, y, irt, c, r, Gecode::IPL_DEF);
199 }
200 };
201
203 class BoolVar : public Test {
204 protected:
209 public:
211 BoolVar(const std::string& s,
212 int min, int max, const Gecode::IntArgs& a0,
214 : Test(TestTags::sweep(),"Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
215 min,max,true),
216 a(a0), irt(irt0) {
217 testfix=false;
218 }
219
220 virtual bool solution(const Assignment& x) const {
221 int n=x.size()-1;
222 for (int i=0; i<n; i++)
223 if ((x[i] < 0) || (x[i] > 1))
224 return false;
225 double e = 0.0;
226 for (int i=0; i<n; i++)
227 e += a[i]*x[i];
228 return cmp(e, irt, static_cast<double>(x[n]));
229 }
230
231 virtual bool ignore(const Assignment& x) const {
232 for (int i=x.size()-1; i--; )
233 if ((x[i] < 0) || (x[i] > 1))
234 return true;
235 return false;
236 }
237
238 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
239 int n=x.size()-1;
241 for (int i=n; i--; )
242 y[i]=Gecode::channel(home,x[i]);
243 if (one(a))
244 Gecode::linear(home, y, irt, x[n]);
245 else
246 Gecode::linear(home, a, y, irt, x[n]);
247 }
248
249 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
251 int n=x.size()-1;
253 for (int i=n; i--; )
254 y[i]=Gecode::channel(home,x[i]);
255 if (one(a))
256 Gecode::linear(home, y, irt, x[n], r);
257 else
258 Gecode::linear(home, a, y, irt, x[n], r);
259 }
260 };
261
263 class Create {
264 public:
266 Create(void) {
267 using namespace Gecode;
268 {
269 IntSet d1(-2,2);
270 const int dv2[] = {-4,-1,0,1,4};
271 IntSet d2(dv2,5);
272
273 const int dv3[] = {0,1500000000};
274 IntSet d3(dv3,2);
275
276 IntArgs a1({0});
277
278 for (IntRelTypes irts; irts(); ++irts) {
279 TestTags tags = irts.irt() == Gecode::IRT_EQ
281 (void) new IntInt(tags,"11",d1,a1,irts.irt(),0);
282 (void) new IntVar("11",d1,a1,irts.irt());
283 (void) new IntInt(TestTags::sweep(),"21",d2,a1,irts.irt(),0);
284 (void) new IntVar("21",d2,a1,irts.irt());
285 (void) new IntInt(TestTags::sweep(),"31",d3,a1,irts.irt(),150000000);
286 }
287 (void) new IntInt(TestTags::sweep(),"11",d1,a1,IRT_EQ,0,IPL_DOM);
288 (void) new IntVar("11",d1,a1,IRT_EQ,IPL_DOM);
289 (void) new IntInt(TestTags::sweep(),"21",d2,a1,IRT_EQ,0,IPL_DOM);
290 (void) new IntVar("21",d2,a1,IRT_EQ,IPL_DOM);
291
292 const int av2[5] = {1,1,1,1,1};
293 const int av3[5] = {1,-1,-1,1,-1};
294 const int av4[5] = {2,3,5,7,11};
295 const int av5[5] = {-2,3,-5,7,-11};
296
297
298 for (int i=1; i<=5; i++) {
299 IntArgs a2(i, av2);
300 IntArgs a3(i, av3);
301 IntArgs a4(i, av4);
302 IntArgs a5(i, av5);
303 for (IntRelTypes irts; irts(); ++irts) {
304 (void) new IntInt(TestTags::sweep(),"12",d1,a2,irts.irt(),0);
305 (void) new IntInt(TestTags::sweep(),"13",d1,a3,irts.irt(),0);
306 (void) new IntInt(TestTags::sweep(),"14",d1,a4,irts.irt(),0);
307 (void) new IntInt(TestTags::sweep(),"15",d1,a5,irts.irt(),0);
308 (void) new IntInt(TestTags::sweep(),"22",d2,a2,irts.irt(),0);
309 (void) new IntInt(TestTags::sweep(),"23",d2,a3,irts.irt(),0);
310 (void) new IntInt(TestTags::sweep(),"24",d2,a4,irts.irt(),0);
311 (void) new IntInt(TestTags::sweep(),"25",d2,a5,irts.irt(),0);
312 (void) new IntInt(TestTags::sweep(),"32",d3,a2,irts.irt(),1500000000);
313 if (i < 5) {
314 (void) new IntVar("12",d1,a2,irts.irt());
315 (void) new IntVar("13",d1,a3,irts.irt());
316 (void) new IntVar("14",d1,a4,irts.irt());
317 (void) new IntVar("15",d1,a5,irts.irt());
318 (void) new IntVar("22",d2,a2,irts.irt());
319 (void) new IntVar("23",d2,a3,irts.irt());
320 (void) new IntVar("24",d2,a4,irts.irt());
321 (void) new IntVar("25",d2,a5,irts.irt());
322 }
323 }
324 (void) new IntInt(TestTags::sweep(),"12",d1,a2,IRT_EQ,0,IPL_DOM);
325 (void) new IntInt(TestTags::sweep(),"13",d1,a3,IRT_EQ,0,IPL_DOM);
326 (void) new IntInt(TestTags::sweep(),"14",d1,a4,IRT_EQ,0,IPL_DOM);
327 (void) new IntInt(TestTags::sweep(),"15",d1,a5,IRT_EQ,0,IPL_DOM);
328 (void) new IntInt(TestTags::sweep(),"22",d2,a2,IRT_EQ,0,IPL_DOM);
329 (void) new IntInt(TestTags::sweep(),"23",d2,a3,IRT_EQ,0,IPL_DOM);
330 (void) new IntInt(TestTags::sweep(),"24",d2,a4,IRT_EQ,0,IPL_DOM);
331 (void) new IntInt(TestTags::sweep(),"25",d2,a5,IRT_EQ,0,IPL_DOM);
332 if (i < 4) {
333 (void) new IntVar("12",d1,a2,IRT_EQ,IPL_DOM);
334 (void) new IntVar("13",d1,a3,IRT_EQ,IPL_DOM);
335 (void) new IntVar("14",d1,a4,IRT_EQ,IPL_DOM);
336 (void) new IntVar("15",d1,a5,IRT_EQ,IPL_DOM);
337 }
338 }
339 }
340 {
341 const int av1[10] = {
342 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
343 };
344 const int av2[10] = {
345 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
346 };
347
348 for (int i=1; i<=10; i += 3) {
349 IntArgs a1(i, av1);
350 IntArgs a2(i, av2);
351 for (int c=0; c<=6; c++)
352 for (IntRelTypes irts; irts(); ++irts) {
353 (void) new BoolInt("1",a1,irts.irt(),c);
354 (void) new BoolInt("2",a2,irts.irt(),-c);
355 }
356 }
357
358 IntArgs a3({1,2,3,4,5});
359 IntArgs a4({-1,-2,-3,-4,-5});
360 IntArgs a5({-1,-2,1,2,4});
361
362 for (IntRelTypes irts; irts(); ++irts) {
363 for (int c=0; c<=16; c++) {
364 (void) new BoolInt("3",a3,irts.irt(),c);
365 (void) new BoolInt("4",a4,irts.irt(),-c);
366 (void) new BoolInt("5",a5,irts.irt(),c);
367 (void) new BoolInt("6",a5,irts.irt(),-c);
368 }
369 }
370
371 for (int i=1; i<=5; i += 2) {
372 IntArgs a1(i, av1);
373 IntArgs a2(i, av2);
374 for (IntRelTypes irts; irts(); ++irts) {
375 (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
376 (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
377 }
378 }
379
380 IntArgs a6({1,2,3,4});
381 IntArgs a7({-1,-2,-3,-4});
382 IntArgs a8({-1,-2,1,2});
383 IntArgs a9({-1,-2,1,2,-3,3});
384
385 for (IntRelTypes irts; irts(); ++irts) {
386 (void) new BoolVar("6",0,10,a6,irts.irt());
387 (void) new BoolVar("7",-10,0,a7,irts.irt());
388 (void) new BoolVar("8",-3,3,a8,irts.irt());
389 (void) new BoolVar("9",-3,3,a9,irts.irt());
390 }
391
392 }
393 }
394 };
395
398
399 }
400}}
401
402// STATISTICS: test-int
Passing Boolean variables.
Definition int.hh:739
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Passing integer arguments.
Definition int.hh:653
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Reification specification.
Definition int.hh:1176
Computation spaces.
Definition core.hpp:1787
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
TestTags tags(void) const
Return tags for test.
Definition test.hpp:95
Base class for assignments
Definition int.hh:73
int size(void) const
Return number of variables.
Definition int.hpp:46
Iterator for integer relation types.
Definition int.hh:466
Test linear relation over Boolean variables equal to constant
Definition linear.cpp:152
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:155
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:173
int c
Righthand-side constant.
Definition linear.cpp:159
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:180
BoolInt(const std::string &s, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0)
Create and register test.
Definition linear.cpp:162
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:157
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:190
Test linear relation over Boolean variables equal to integer variable
Definition linear.cpp:203
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:208
BoolVar(const std::string &s, int min, int max, const Gecode::IntArgs &a0, Gecode::IntRelType irt0)
Create and register test.
Definition linear.cpp:211
virtual bool ignore(const Assignment &x) const
Test whether x is to be ignored
Definition linear.cpp:231
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:220
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:238
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:249
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:206
Help class to create and register tests.
Definition linear.cpp:263
Create(void)
Perform creation and registration.
Definition linear.cpp:266
Test linear relation over integer variables
Definition linear.cpp:57
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:62
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:60
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:85
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:92
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:78
IntInt(TestTags tags, const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
Create and register test.
Definition linear.cpp:67
Test linear relation over integer variables
Definition linear.cpp:102
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:138
IntVar(const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
Create and register test.
Definition linear.cpp:110
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:105
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:120
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:127
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:107
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
bool testfix
Whether to perform fixpoint test.
Definition int.hh:287
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition int.hpp:296
Set of test tags.
Definition test.hh:105
static TestTags sweep(void)
Expensive parameter sweeps.
Definition test.hpp:59
static TestTags standard(void)
Standard suite without expensive sweeps.
Definition test.hpp:55
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
IntRelType
Relation types for integers.
Definition int.hh:1225
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
@ IPL_BND
Bounds propagation.
Definition int.hh:1278
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Tests for linear constraints
Definition linear.cpp:41
bool one(const Gecode::IntArgs &a)
Check whether a has only one coefficients.
Definition linear.cpp:44
Testing finite domain integers.
Definition int.cpp:41
General test support.
Definition afc.cpp:41
Region r
Definition region.cpp:65
@ check
Basic integrity tests.
Definition test.hh:99
@ sweep
Really heavy sweep tests.
Definition test.hh:101