Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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
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
57 class IntInt : public Test {
58 protected:
64 int c;
65 public:
67 IntInt(const std::string& s, const Gecode::IntSet& d,
68 const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
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 }
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 }
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 }
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("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 }
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 }
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 }
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("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 }
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 }
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))
184 else
185 Gecode::linear(home, a, y, irt, c, Gecode::IPL_DEF);
186 }
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
201 class BoolVar : public Test {
202 protected:
207 public:
209 BoolVar(const std::string& s,
210 int min, int max, const Gecode::IntArgs& a0,
212 : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
213 min,max,true),
214 a(a0), irt(irt0) {
215 testfix=false;
216 }
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 }
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 }
236 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
237 int n=x.size()-1;
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 }
249 int n=x.size()-1;
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
261 class Create {
262 public:
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
394
395 }
396}}
397
398// STATISTICS: test-int
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Passing Boolean variables.
Definition int.hh:712
Passing integer arguments.
Definition int.hh:628
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Reification specification.
Definition int.hh:876
Computation spaces.
Definition core.hpp:1742
Base class for assignments
Definition int.hh:59
Iterator for integer relation types.
Definition int.hh:368
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:171
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:178
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:188
Test linear relation over Boolean variables equal to integer variable
Definition linear.cpp:201
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:206
BoolVar(const std::string &s, int min, int max, const Gecode::IntArgs &a0, Gecode::IntRelType irt0)
Create and register test.
Definition linear.cpp:209
virtual bool ignore(const Assignment &x) const
Test whether x is to be ignored
Definition linear.cpp:229
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:218
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:236
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:247
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:204
Help class to create and register tests.
Definition linear.cpp:261
Create(void)
Perform creation and registration.
Definition linear.cpp:264
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(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
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:234
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition int.hpp:285
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:925
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
@ IPL_DEF
Simple propagation levels.
Definition int.hh:976
@ IPL_BND
Bounds propagation.
Definition int.hh:978
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
bool one(const Gecode::IntArgs &a)
Check whether a has only one coefficients.
Definition linear.cpp:44
General test support.
Definition afc.cpp:39
Region r
Definition region.cpp:65