Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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 
38 namespace 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  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  }
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 
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  }
138  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
139  Gecode::Reify r) {
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  }
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 
201  class BoolVar : public Test {
202  protected:
207  public:
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  }
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  }
247  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
248  Gecode::Reify r) {
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
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:206
IntRelType
Relation types for integers.
Definition: int.hh:925
Region r
Definition: region.cpp:65
Iterator for integer relation types.
Definition: int.hh:368
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:138
Create c
Definition: linear.cpp:392
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:247
Gecode::IntPropLevel ipl
Propagation level.
Definition: int.hh:234
Test linear relation over integer variables
Definition: linear.cpp:102
BoolVar(const std::string &s, int min, int max, const Gecode::IntArgs &a0, Gecode::IntRelType irt0)
Create and register test.
Definition: linear.cpp:209
Passing integer variables.
Definition: int.hh:656
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:107
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:62
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Test linear relation over Boolean variables equal to integer variable
Definition: linear.cpp:201
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
Computation spaces.
Definition: core.hpp:1742
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:178
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:78
Integer variable array.
Definition: int.hh:763
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition: int.hpp:285
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:204
Gecode toplevel namespace
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:240
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:236
Integer sets.
Definition: int.hh:174
Help class to create and register tests.
Definition: linear.cpp:261
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:105
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Reification specification.
Definition: int.hh:876
Passing Boolean variables.
Definition: int.hh:712
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
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:120
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:218
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:155
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
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
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:157
Bounds propagation.
Definition: int.hh:978
Test linear relation over integer variables
Definition: linear.cpp:57
Gecode::IntSet d1(v1, 7)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:127
Base class for assignments
Definition: int.hh:59
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:92
int c
Righthand-side constant.
Definition: linear.cpp:159
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Gecode::IntSet d2(v2, 9)
Simple propagation levels.
Definition: int.hh:976
Gecode::IntSet d(v, 7)
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: channel.cpp:41
virtual bool ignore(const Assignment &x) const
Test whether x is to be ignored
Definition: linear.cpp:229
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:188
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:171
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:60
General test support.
Definition: afc.cpp:39
Equality ( )
Definition: int.hh:926
int c
Result.
Definition: linear.cpp:64
BoolInt(const std::string &s, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0)
Create and register test.
Definition: linear.cpp:162
Gecode::IntSet d3(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:85
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
Test linear relation over Boolean variables equal to constant
Definition: linear.cpp:152
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
bool one(const Gecode::IntArgs &a)
Check whether a has only one coefficients.
Definition: linear.cpp:44
Create(void)
Perform creation and registration.
Definition: linear.cpp:264
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition: int.hpp:209