Generated on Wed Sep 5 2012 18:52:07 for Gecode by doxygen 1.8.1.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: 2011-09-02 21:27:53 +1000 (Fri, 02 Sep 2011) $ by $Author: tack $
11  * $Revision: 12389 $
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 
61  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) {}
80  virtual bool solution(const Assignment& x) const {
81  double e = 0.0;
82  for (int i=0; i<x.size(); i++)
83  e += a[i]*x[i];
84  return cmp(e, irt, static_cast<double>(c));
85  }
87  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
88  if (one(a))
89  Gecode::linear(home, x, irt, c, icl);
90  else
91  Gecode::linear(home, a, x, irt, c, icl);
92  }
94  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
96  if (one(a))
97  Gecode::linear(home, x, irt, c, b, icl);
98  else
99  Gecode::linear(home, a, x, irt, c, b, icl);
100  }
101  };
102 
104  class IntVar : public Test {
105  protected:
110  public:
112  IntVar(const std::string& s, const Gecode::IntSet& d,
113  const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
115  : Test("Linear::Int::Var::"+
116  str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()),
117  a0.size()+1,d,icl != Gecode::ICL_DOM,icl),
118  a(a0), irt(irt0) {}
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();
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], icl);
134  else
135  Gecode::linear(home, a, y, irt, x[n], icl);
136  }
138  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
139  Gecode::BoolVar b) {
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], b, icl);
146  else
147  Gecode::linear(home, a, y, irt, x[n], b, icl);
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::ICL_DEF),
167  a(a0), irt(irt0), c(c0) {
168  }
170  virtual bool solution(const Assignment& x) const {
171  double e = 0.0;
172  for (int i=0; i<x.size(); i++)
173  e += a[i]*x[i];
174  return cmp(e, irt, static_cast<double>(c));
175  }
177  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
178  Gecode::BoolVarArgs y(x.size());
179  for (int i=x.size(); i--; )
180  y[i]=Gecode::channel(home,x[i]);
181  if (one(a))
182  Gecode::linear(home, y, irt, c, Gecode::ICL_DEF);
183  else
184  Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF);
185  }
187  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
188  Gecode::BoolVar b) {
189  Gecode::BoolVarArgs y(x.size());
190  for (int i=x.size(); i--; )
191  y[i]=Gecode::channel(home,x[i]);
192  if (one(a))
193  Gecode::linear(home, y, irt, c, b, Gecode::ICL_DEF);
194  else
195  Gecode::linear(home, a, y, irt, c, b, Gecode::ICL_DEF);
196  }
197  };
198 
200  class BoolVar : public Test {
201  protected:
206  public:
208  BoolVar(const std::string& s,
209  int min, int max, const Gecode::IntArgs& a0,
210  Gecode::IntRelType irt0)
211  : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
212  min,max,true),
213  a(a0), irt(irt0) {}
215  virtual bool solution(const Assignment& x) const {
216  int n=x.size()-1;
217  for (int i=0; i<n; i++)
218  if ((x[i] < 0) || (x[i] > 1))
219  return false;
220  double e = 0.0;
221  for (int i=0; i<n; i++)
222  e += a[i]*x[i];
223  return cmp(e, irt, static_cast<double>(x[n]));
224  }
226  virtual bool ignore(const Assignment& x) const {
227  for (int i=x.size()-1; i--; )
228  if ((x[i] < 0) || (x[i] > 1))
229  return true;
230  return false;
231  }
233  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
234  int n=x.size()-1;
235  Gecode::BoolVarArgs y(n);
236  for (int i=n; i--; )
237  y[i]=Gecode::channel(home,x[i]);
238  if (one(a))
239  Gecode::linear(home, y, irt, x[n]);
240  else
241  Gecode::linear(home, a, y, irt, x[n]);
242  }
244  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
245  Gecode::BoolVar b) {
246  int n=x.size()-1;
247  Gecode::BoolVarArgs y(n);
248  for (int i=n; i--; )
249  y[i]=Gecode::channel(home,x[i]);
250  if (one(a))
251  Gecode::linear(home, y, irt, x[n], b);
252  else
253  Gecode::linear(home, a, y, irt, x[n], b);
254  }
255  };
256 
258  class Create {
259  public:
261  Create(void) {
262  using namespace Gecode;
263  {
264  IntSet d1(-2,2);
265  const int dv2[] = {-4,-1,0,1,4};
266  IntSet d2(dv2,5);
267 
268  const int dv3[] = {0,1500000000};
269  IntSet d3(dv3,2);
270 
271  IntArgs a1(1, 0);
272 
273  for (IntRelTypes irts; irts(); ++irts) {
274  (void) new IntInt("11",d1,a1,irts.irt(),0);
275  (void) new IntVar("11",d1,a1,irts.irt());
276  (void) new IntInt("21",d2,a1,irts.irt(),0);
277  (void) new IntVar("21",d2,a1,irts.irt());
278  (void) new IntInt("31",d3,a1,irts.irt(),150000000);
279  }
280  (void) new IntInt("11",d1,a1,IRT_EQ,0,ICL_DOM);
281  (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM);
282  (void) new IntInt("21",d2,a1,IRT_EQ,0,ICL_DOM);
283  (void) new IntVar("21",d2,a1,IRT_EQ,ICL_DOM);
284 
285  const int av2[5] = {1,1,1,1,1};
286  const int av3[5] = {1,-1,-1,1,-1};
287  const int av4[5] = {2,3,5,7,11};
288  const int av5[5] = {-2,3,-5,7,-11};
289 
290  for (int i=1; i<=5; i++) {
291  IntArgs a2(i, av2);
292  IntArgs a3(i, av3);
293  IntArgs a4(i, av4);
294  IntArgs a5(i, av5);
295  for (IntRelTypes irts; irts(); ++irts) {
296  (void) new IntInt("12",d1,a2,irts.irt(),0);
297  (void) new IntInt("13",d1,a3,irts.irt(),0);
298  (void) new IntInt("14",d1,a4,irts.irt(),0);
299  (void) new IntInt("15",d1,a5,irts.irt(),0);
300  (void) new IntInt("22",d2,a2,irts.irt(),0);
301  (void) new IntInt("23",d2,a3,irts.irt(),0);
302  (void) new IntInt("24",d2,a4,irts.irt(),0);
303  (void) new IntInt("25",d2,a5,irts.irt(),0);
304  (void) new IntInt("32",d3,a2,irts.irt(),1500000000);
305  if (i < 5) {
306  (void) new IntVar("12",d1,a2,irts.irt());
307  (void) new IntVar("13",d1,a3,irts.irt());
308  (void) new IntVar("14",d1,a4,irts.irt());
309  (void) new IntVar("15",d1,a5,irts.irt());
310  (void) new IntVar("22",d2,a2,irts.irt());
311  (void) new IntVar("23",d2,a3,irts.irt());
312  (void) new IntVar("24",d2,a4,irts.irt());
313  (void) new IntVar("25",d2,a5,irts.irt());
314  }
315  }
316  (void) new IntInt("12",d1,a2,IRT_EQ,0,ICL_DOM);
317  (void) new IntInt("13",d1,a3,IRT_EQ,0,ICL_DOM);
318  (void) new IntInt("14",d1,a4,IRT_EQ,0,ICL_DOM);
319  (void) new IntInt("15",d1,a5,IRT_EQ,0,ICL_DOM);
320  (void) new IntInt("22",d2,a2,IRT_EQ,0,ICL_DOM);
321  (void) new IntInt("23",d2,a3,IRT_EQ,0,ICL_DOM);
322  (void) new IntInt("24",d2,a4,IRT_EQ,0,ICL_DOM);
323  (void) new IntInt("25",d2,a5,IRT_EQ,0,ICL_DOM);
324  if (i < 4) {
325  (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM);
326  (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM);
327  (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM);
328  (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM);
329  }
330  }
331  }
332  {
333  const int av1[10] = {
334  1, 1, 1, 1, 1, 1, 1, 1, 1, 1
335  };
336  const int av2[10] = {
337  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
338  };
339 
340  for (int i=1; i<=10; i += 3) {
341  IntArgs a1(i, av1);
342  IntArgs a2(i, av2);
343  for (int c=0; c<=6; c++)
344  for (IntRelTypes irts; irts(); ++irts) {
345  (void) new BoolInt("1",a1,irts.irt(),c);
346  (void) new BoolInt("2",a2,irts.irt(),-c);
347  }
348  }
349 
350  IntArgs a3(5, 1,2,3,4,5);
351  IntArgs a4(5, -1,-2,-3,-4,-5);
352  IntArgs a5(5, -1,-2,1,2,4);
353 
354  for (IntRelTypes irts; irts(); ++irts) {
355  for (int c=0; c<=16; c++) {
356  (void) new BoolInt("3",a3,irts.irt(),c);
357  (void) new BoolInt("4",a4,irts.irt(),-c);
358  (void) new BoolInt("5",a5,irts.irt(),c);
359  (void) new BoolInt("6",a5,irts.irt(),-c);
360  }
361  }
362 
363  for (int i=1; i<=5; i += 2) {
364  IntArgs a1(i, av1);
365  IntArgs a2(i, av2);
366  for (IntRelTypes irts; irts(); ++irts) {
367  (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
368  (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
369  }
370  }
371 
372  IntArgs a6(4, 1,2,3,4);
373  IntArgs a7(4, -1,-2,-3,-4);
374  IntArgs a8(4, -1,-2,1,2);
375  IntArgs a9(6, -1,-2,1,2,-3,3);
376 
377  for (IntRelTypes irts; irts(); ++irts) {
378  (void) new BoolVar("6",0,10,a6,irts.irt());
379  (void) new BoolVar("7",-10,0,a7,irts.irt());
380  (void) new BoolVar("8",-3,3,a8,irts.irt());
381  (void) new BoolVar("9",-3,3,a9,irts.irt());
382  }
383 
384  }
385  }
386  };
387 
390 
391  }
392 }}
393 
394 // STATISTICS: test-int