Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.1
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  * Last modified:
10  * $Date: 2012-10-18 16:02:42 +0200 (Thu, 18 Oct 2012) $ by $Author: schulte $
11  * $Revision: 13154 $
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 "test/int.hh"
39 
40 #include <gecode/minimodel.hh>
41 
42 namespace Test { namespace Int {
43 
45  namespace Linear {
46 
48  bool one(const Gecode::IntArgs& a) {
49  for (int i=a.size(); i--; )
50  if (a[i] != 1)
51  return false;
52  return true;
53  }
54 
60  class IntInt : public Test {
62  protected:
68  int c;
69  public:
71  IntInt(const std::string& s, const Gecode::IntSet& d,
72  const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
74  : Test("Linear::Int::Int::"+
75  str(irt0)+"::"+str(icl)+"::"+s+"::"+str(c0)+"::"
76  +str(a0.size()),
77  a0.size(),d,icl != Gecode::ICL_DOM,icl),
78  a(a0), irt(irt0), c(c0) {
79  testfix=false;
80  }
82  virtual bool solution(const Assignment& x) const {
83  double e = 0.0;
84  for (int i=0; i<x.size(); i++)
85  e += a[i]*x[i];
86  return cmp(e, irt, static_cast<double>(c));
87  }
89  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
90  if (one(a))
91  Gecode::linear(home, x, irt, c, icl);
92  else
93  Gecode::linear(home, a, x, irt, c, icl);
94  }
96  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
97  Gecode::Reify r) {
98  if (one(a))
99  Gecode::linear(home, x, irt, c, r, icl);
100  else
101  Gecode::linear(home, a, x, irt, c, r, icl);
102  }
103  };
104 
106  class IntVar : public Test {
107  protected:
112  public:
114  IntVar(const std::string& s, const Gecode::IntSet& d,
115  const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
117  : Test("Linear::Int::Var::"+
118  str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()),
119  a0.size()+1,d,icl != Gecode::ICL_DOM,icl),
120  a(a0), irt(irt0) {
121  testfix=false;
122  }
124  virtual bool solution(const Assignment& x) const {
125  double e = 0.0;
126  for (int i=0; i<a.size(); i++)
127  e += a[i]*x[i];
128  return cmp(e, irt, static_cast<double>(x[a.size()]));
129  }
131  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
132  int n = a.size();
133  Gecode::IntVarArgs y(n);
134  for (int i=n; i--; )
135  y[i] = x[i];
136  if (one(a))
137  Gecode::linear(home, y, irt, x[n], icl);
138  else
139  Gecode::linear(home, a, y, irt, x[n], icl);
140  }
142  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
143  Gecode::Reify r) {
144  int n = a.size();
145  Gecode::IntVarArgs y(n);
146  for (int i=n; i--; )
147  y[i] = x[i];
148  if (one(a))
149  Gecode::linear(home, y, irt, x[n], r, icl);
150  else
151  Gecode::linear(home, a, y, irt, x[n], r, icl);
152  }
153  };
154 
156  class BoolInt : public Test {
157  protected:
163  int c;
164  public:
166  BoolInt(const std::string& s, const Gecode::IntArgs& a0,
167  Gecode::IntRelType irt0, int c0)
168  : Test("Linear::Bool::Int::"+
169  str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
170  a0.size(),0,1,true,Gecode::ICL_DEF),
171  a(a0), irt(irt0), c(c0) {
172  testfix=false;
173  }
175  virtual bool solution(const Assignment& x) const {
176  double e = 0.0;
177  for (int i=0; i<x.size(); i++)
178  e += a[i]*x[i];
179  return cmp(e, irt, static_cast<double>(c));
180  }
182  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
183  Gecode::BoolVarArgs y(x.size());
184  for (int i=x.size(); i--; )
185  y[i]=Gecode::channel(home,x[i]);
186  if (one(a))
187  Gecode::linear(home, y, irt, c, Gecode::ICL_DEF);
188  else
189  Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF);
190  }
192  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
193  Gecode::Reify r) {
194  Gecode::BoolVarArgs y(x.size());
195  for (int i=x.size(); i--; )
196  y[i]=Gecode::channel(home,x[i]);
197  if (one(a))
198  Gecode::linear(home, y, irt, c, r, Gecode::ICL_DEF);
199  else
200  Gecode::linear(home, a, y, irt, c, r, Gecode::ICL_DEF);
201  }
202  };
203 
205  class BoolVar : public Test {
206  protected:
211  public:
213  BoolVar(const std::string& s,
214  int min, int max, const Gecode::IntArgs& a0,
215  Gecode::IntRelType irt0)
216  : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
217  min,max,true),
218  a(a0), irt(irt0) {
219  testfix=false;
220  }
222  virtual bool solution(const Assignment& x) const {
223  int n=x.size()-1;
224  for (int i=0; i<n; i++)
225  if ((x[i] < 0) || (x[i] > 1))
226  return false;
227  double e = 0.0;
228  for (int i=0; i<n; i++)
229  e += a[i]*x[i];
230  return cmp(e, irt, static_cast<double>(x[n]));
231  }
233  virtual bool ignore(const Assignment& x) const {
234  for (int i=x.size()-1; i--; )
235  if ((x[i] < 0) || (x[i] > 1))
236  return true;
237  return false;
238  }
240  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
241  int n=x.size()-1;
242  Gecode::BoolVarArgs y(n);
243  for (int i=n; i--; )
244  y[i]=Gecode::channel(home,x[i]);
245  if (one(a))
246  Gecode::linear(home, y, irt, x[n]);
247  else
248  Gecode::linear(home, a, y, irt, x[n]);
249  }
251  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
252  Gecode::Reify r) {
253  int n=x.size()-1;
254  Gecode::BoolVarArgs y(n);
255  for (int i=n; i--; )
256  y[i]=Gecode::channel(home,x[i]);
257  if (one(a))
258  Gecode::linear(home, y, irt, x[n], r);
259  else
260  Gecode::linear(home, a, y, irt, x[n], r);
261  }
262  };
263 
265  class Create {
266  public:
268  Create(void) {
269  using namespace Gecode;
270  {
271  IntSet d1(-2,2);
272  const int dv2[] = {-4,-1,0,1,4};
273  IntSet d2(dv2,5);
274 
275  const int dv3[] = {0,1500000000};
276  IntSet d3(dv3,2);
277 
278  IntArgs a1(1, 0);
279 
280  for (IntRelTypes irts; irts(); ++irts) {
281  (void) new IntInt("11",d1,a1,irts.irt(),0);
282  (void) new IntVar("11",d1,a1,irts.irt());
283  (void) new IntInt("21",d2,a1,irts.irt(),0);
284  (void) new IntVar("21",d2,a1,irts.irt());
285  (void) new IntInt("31",d3,a1,irts.irt(),150000000);
286  }
287  (void) new IntInt("11",d1,a1,IRT_EQ,0,ICL_DOM);
288  (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM);
289  (void) new IntInt("21",d2,a1,IRT_EQ,0,ICL_DOM);
290  (void) new IntVar("21",d2,a1,IRT_EQ,ICL_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  for (int i=1; i<=5; i++) {
298  IntArgs a2(i, av2);
299  IntArgs a3(i, av3);
300  IntArgs a4(i, av4);
301  IntArgs a5(i, av5);
302  for (IntRelTypes irts; irts(); ++irts) {
303  (void) new IntInt("12",d1,a2,irts.irt(),0);
304  (void) new IntInt("13",d1,a3,irts.irt(),0);
305  (void) new IntInt("14",d1,a4,irts.irt(),0);
306  (void) new IntInt("15",d1,a5,irts.irt(),0);
307  (void) new IntInt("22",d2,a2,irts.irt(),0);
308  (void) new IntInt("23",d2,a3,irts.irt(),0);
309  (void) new IntInt("24",d2,a4,irts.irt(),0);
310  (void) new IntInt("25",d2,a5,irts.irt(),0);
311  (void) new IntInt("32",d3,a2,irts.irt(),1500000000);
312  if (i < 5) {
313  (void) new IntVar("12",d1,a2,irts.irt());
314  (void) new IntVar("13",d1,a3,irts.irt());
315  (void) new IntVar("14",d1,a4,irts.irt());
316  (void) new IntVar("15",d1,a5,irts.irt());
317  (void) new IntVar("22",d2,a2,irts.irt());
318  (void) new IntVar("23",d2,a3,irts.irt());
319  (void) new IntVar("24",d2,a4,irts.irt());
320  (void) new IntVar("25",d2,a5,irts.irt());
321  }
322  }
323  (void) new IntInt("12",d1,a2,IRT_EQ,0,ICL_DOM);
324  (void) new IntInt("13",d1,a3,IRT_EQ,0,ICL_DOM);
325  (void) new IntInt("14",d1,a4,IRT_EQ,0,ICL_DOM);
326  (void) new IntInt("15",d1,a5,IRT_EQ,0,ICL_DOM);
327  (void) new IntInt("22",d2,a2,IRT_EQ,0,ICL_DOM);
328  (void) new IntInt("23",d2,a3,IRT_EQ,0,ICL_DOM);
329  (void) new IntInt("24",d2,a4,IRT_EQ,0,ICL_DOM);
330  (void) new IntInt("25",d2,a5,IRT_EQ,0,ICL_DOM);
331  if (i < 4) {
332  (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM);
333  (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM);
334  (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM);
335  (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM);
336  }
337  }
338  }
339  {
340  const int av1[10] = {
341  1, 1, 1, 1, 1, 1, 1, 1, 1, 1
342  };
343  const int av2[10] = {
344  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
345  };
346 
347  for (int i=1; i<=10; i += 3) {
348  IntArgs a1(i, av1);
349  IntArgs a2(i, av2);
350  for (int c=0; c<=6; c++)
351  for (IntRelTypes irts; irts(); ++irts) {
352  (void) new BoolInt("1",a1,irts.irt(),c);
353  (void) new BoolInt("2",a2,irts.irt(),-c);
354  }
355  }
356 
357  IntArgs a3(5, 1,2,3,4,5);
358  IntArgs a4(5, -1,-2,-3,-4,-5);
359  IntArgs a5(5, -1,-2,1,2,4);
360 
361  for (IntRelTypes irts; irts(); ++irts) {
362  for (int c=0; c<=16; c++) {
363  (void) new BoolInt("3",a3,irts.irt(),c);
364  (void) new BoolInt("4",a4,irts.irt(),-c);
365  (void) new BoolInt("5",a5,irts.irt(),c);
366  (void) new BoolInt("6",a5,irts.irt(),-c);
367  }
368  }
369 
370  for (int i=1; i<=5; i += 2) {
371  IntArgs a1(i, av1);
372  IntArgs a2(i, av2);
373  for (IntRelTypes irts; irts(); ++irts) {
374  (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
375  (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
376  }
377  }
378 
379  IntArgs a6(4, 1,2,3,4);
380  IntArgs a7(4, -1,-2,-3,-4);
381  IntArgs a8(4, -1,-2,1,2);
382  IntArgs a9(6, -1,-2,1,2,-3,3);
383 
384  for (IntRelTypes irts; irts(); ++irts) {
385  (void) new BoolVar("6",0,10,a6,irts.irt());
386  (void) new BoolVar("7",-10,0,a7,irts.irt());
387  (void) new BoolVar("8",-3,3,a8,irts.irt());
388  (void) new BoolVar("9",-3,3,a9,irts.irt());
389  }
390 
391  }
392  }
393  };
394 
397 
398  }
399 }}
400 
401 // STATISTICS: test-int
bool one(const Gecode::IntArgs &a)
Check whether a has only one coefficients.
Definition: linear.cpp:48
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:182
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: arithmetic.cpp:218
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
IntVar(const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, Gecode::IntConLevel icl=Gecode::ICL_BND)
Create and register test.
Definition: linear.cpp:114
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition: int.hpp:284
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:210
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:124
int c
Righthand-side constant.
Definition: linear.cpp:163
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:82
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:251
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:240
Integer variable array.
Definition: int.hh:741
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:111
BoolVar(const std::string &s, int min, int max, const Gecode::IntArgs &a0, Gecode::IntRelType irt0)
Create and register test.
Definition: linear.cpp:213
Computation spaces.
Definition: core.hpp:1362
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:131
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:159
BoolInt(const std::string &s, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0)
Create and register test.
Definition: linear.cpp:166
Help class to create and register tests.
Definition: linear.cpp:265
Gecode::IntSet d1(v1, 7)
Gecode::IntSet d(v, 7)
static std::string str(Gecode::ExtensionalPropKind epk)
Map extensional propagation kind to string.
Definition: int.hpp:212
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
Gecode::IntSet d2(v2, 9)
virtual bool ignore(const Assignment &x) const
Test whether x is to be ignored
Definition: linear.cpp:233
Gecode::IntConLevel icl
Consistency level.
Definition: int.hh:226
IntRelType
Relation types for integers.
Definition: int.hh:903
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:64
Iterator for integer relation types.
Definition: int.hh:342
unsigned int size(I &i)
Size of all ranges of range iterator i.
Test linear relation over Boolean variables equal to constant
Definition: linear.cpp:156
Reification specification.
Definition: int.hh:854
Gecode::IntSet d3(-8, 8)
Integer sets.
Definition: int.hh:171
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:192
IntInt(const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0, Gecode::IntConLevel icl=Gecode::ICL_BND)
Create and register test.
Definition: linear.cpp:71
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:142
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:208
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:175
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:232
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:161
General test support.
Definition: afc.cpp:43
Test linear relation over integer variables
Definition: linear.cpp:106
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Test linear relation over integer variables
Definition: linear.cpp:61
Gecode::IntRelType irt
Integer relation type to propagate.
Definition: linear.cpp:66
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition: linear.cpp:96
Base class for assignments
Definition: int.hh:63
The default consistency for a constraint.
Definition: int.hh:941
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: linear.cpp:89
Bounds propagation or consistency.
Definition: int.hh:939
Gecode toplevel namespace
Create(void)
Perform creation and registration.
Definition: linear.cpp:268
Test linear relation over Boolean variables equal to integer variable
Definition: linear.cpp:205
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
Gecode::IntArgs a
Coefficients.
Definition: linear.cpp:109
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
int size(void) const
Return number of variables.
Definition: int.hpp:50
Domain propagation or consistency.
Definition: int.hh:940
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: linear.cpp:222