linear.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include "test/int.hh" 00039 00040 #include <gecode/minimodel.hh> 00041 00042 namespace Test { namespace Int { 00043 00045 namespace Linear { 00046 00048 bool one(const Gecode::IntArgs& a) { 00049 for (int i=a.size(); i--; ) 00050 if (a[i] != 1) 00051 return false; 00052 return true; 00053 } 00054 00060 00061 class IntInt : public Test { 00062 protected: 00064 Gecode::IntArgs a; 00066 Gecode::IntRelType irt; 00067 public: 00069 IntInt(const std::string& s, const Gecode::IntSet& d, 00070 const Gecode::IntArgs& a0, Gecode::IntRelType irt0, 00071 Gecode::IntConLevel icl=Gecode::ICL_BND) 00072 : Test("Linear::Int::Int::"+ 00073 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()), 00074 a0.size(),d,icl != Gecode::ICL_DOM,icl), 00075 a(a0), irt(irt0) {} 00077 virtual bool solution(const Assignment& x) const { 00078 double e = 0.0; 00079 for (int i=0; i<x.size(); i++) 00080 e += a[i]*x[i]; 00081 return cmp(e, irt, static_cast<double>(0)); 00082 } 00084 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00085 if (one(a)) 00086 Gecode::linear(home, x, irt, 0, icl); 00087 else 00088 Gecode::linear(home, a, x, irt, 0, icl); 00089 } 00091 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x, 00092 Gecode::BoolVar b) { 00093 if (one(a)) 00094 Gecode::linear(home, x, irt, 0, b, icl); 00095 else 00096 Gecode::linear(home, a, x, irt, 0, b, icl); 00097 } 00098 }; 00099 00101 class IntVar : public Test { 00102 protected: 00104 Gecode::IntArgs a; 00106 Gecode::IntRelType irt; 00107 public: 00109 IntVar(const std::string& s, const Gecode::IntSet& d, 00110 const Gecode::IntArgs& a0, Gecode::IntRelType irt0, 00111 Gecode::IntConLevel icl=Gecode::ICL_BND) 00112 : Test("Linear::Int::Var::"+ 00113 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()), 00114 a0.size()+1,d,icl != Gecode::ICL_DOM,icl), 00115 a(a0), irt(irt0) {} 00117 virtual bool solution(const Assignment& x) const { 00118 double e = 0.0; 00119 for (int i=0; i<a.size(); i++) 00120 e += a[i]*x[i]; 00121 return cmp(e, irt, static_cast<double>(x[a.size()])); 00122 } 00124 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00125 int n = a.size(); 00126 Gecode::IntVarArgs y(n); 00127 for (int i=n; i--; ) 00128 y[i] = x[i]; 00129 if (one(a)) 00130 Gecode::linear(home, y, irt, x[n], icl); 00131 else 00132 Gecode::linear(home, a, y, irt, x[n], icl); 00133 } 00135 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x, 00136 Gecode::BoolVar b) { 00137 int n = a.size(); 00138 Gecode::IntVarArgs y(n); 00139 for (int i=n; i--; ) 00140 y[i] = x[i]; 00141 if (one(a)) 00142 Gecode::linear(home, y, irt, x[n], b, icl); 00143 else 00144 Gecode::linear(home, a, y, irt, x[n], b, icl); 00145 } 00146 }; 00147 00149 class BoolInt : public Test { 00150 protected: 00152 Gecode::IntArgs a; 00154 Gecode::IntRelType irt; 00156 int c; 00157 public: 00159 BoolInt(const std::string& s, const Gecode::IntArgs& a0, 00160 Gecode::IntRelType irt0, int c0) 00161 : Test("Linear::Bool::Int::"+ 00162 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0), 00163 a0.size(),0,1,true,Gecode::ICL_DEF), 00164 a(a0), irt(irt0), c(c0) { 00165 } 00167 virtual bool solution(const Assignment& x) const { 00168 double e = 0.0; 00169 for (int i=0; i<x.size(); i++) 00170 e += a[i]*x[i]; 00171 return cmp(e, irt, static_cast<double>(c)); 00172 } 00174 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00175 Gecode::BoolVarArgs y(x.size()); 00176 for (int i=x.size(); i--; ) 00177 y[i]=Gecode::channel(home,x[i]); 00178 if (one(a)) 00179 Gecode::linear(home, y, irt, c, Gecode::ICL_DEF); 00180 else 00181 Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF); 00182 } 00184 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x, 00185 Gecode::BoolVar b) { 00186 Gecode::BoolVarArgs y(x.size()); 00187 for (int i=x.size(); i--; ) 00188 y[i]=Gecode::channel(home,x[i]); 00189 if (one(a)) 00190 Gecode::linear(home, y, irt, c, b, Gecode::ICL_DEF); 00191 else 00192 Gecode::linear(home, a, y, irt, c, b, Gecode::ICL_DEF); 00193 } 00194 }; 00195 00197 class BoolVar : public Test { 00198 protected: 00200 Gecode::IntArgs a; 00202 Gecode::IntRelType irt; 00203 public: 00205 BoolVar(const std::string& s, 00206 int min, int max, const Gecode::IntArgs& a0, 00207 Gecode::IntRelType irt0) 00208 : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1, 00209 min,max,true), 00210 a(a0), irt(irt0) {} 00212 virtual bool solution(const Assignment& x) const { 00213 int n=x.size()-1; 00214 for (int i=0; i<n; i++) 00215 if ((x[i] < 0) || (x[i] > 1)) 00216 return false; 00217 double e = 0.0; 00218 for (int i=0; i<n; i++) 00219 e += a[i]*x[i]; 00220 return cmp(e, irt, static_cast<double>(x[n])); 00221 } 00223 virtual bool ignore(const Assignment& x) const { 00224 for (int i=x.size()-1; i--; ) 00225 if ((x[i] < 0) || (x[i] > 1)) 00226 return true; 00227 return false; 00228 } 00230 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00231 int n=x.size()-1; 00232 Gecode::BoolVarArgs y(n); 00233 for (int i=n; i--; ) 00234 y[i]=Gecode::channel(home,x[i]); 00235 if (one(a)) 00236 Gecode::linear(home, y, irt, x[n]); 00237 else 00238 Gecode::linear(home, a, y, irt, x[n]); 00239 } 00241 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x, 00242 Gecode::BoolVar b) { 00243 int n=x.size()-1; 00244 Gecode::BoolVarArgs y(n); 00245 for (int i=n; i--; ) 00246 y[i]=Gecode::channel(home,x[i]); 00247 if (one(a)) 00248 Gecode::linear(home, y, irt, x[n], b); 00249 else 00250 Gecode::linear(home, a, y, irt, x[n], b); 00251 } 00252 }; 00253 00255 class Create { 00256 public: 00258 Create(void) { 00259 using namespace Gecode; 00260 { 00261 IntSet d1(-2,2); 00262 const int dv2[] = {-4,-1,0,1,4}; 00263 IntSet d2(dv2,5); 00264 00265 IntArgs a1(1, 0); 00266 00267 for (IntRelTypes irts; irts(); ++irts) { 00268 (void) new IntInt("11",d1,a1,irts.irt()); 00269 (void) new IntVar("11",d1,a1,irts.irt()); 00270 (void) new IntInt("21",d2,a1,irts.irt()); 00271 (void) new IntVar("21",d2,a1,irts.irt()); 00272 } 00273 (void) new IntInt("11",d1,a1,IRT_EQ,ICL_DOM); 00274 (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM); 00275 (void) new IntInt("21",d2,a1,IRT_EQ,ICL_DOM); 00276 (void) new IntVar("21",d2,a1,IRT_EQ,ICL_DOM); 00277 00278 const int av2[5] = {1,1,1,1,1}; 00279 const int av3[5] = {1,-1,-1,1,-1}; 00280 const int av4[5] = {2,3,5,7,11}; 00281 const int av5[5] = {-2,3,-5,7,-11}; 00282 00283 for (int i=1; i<=5; i++) { 00284 IntArgs a2(i, av2); 00285 IntArgs a3(i, av3); 00286 IntArgs a4(i, av4); 00287 IntArgs a5(i, av5); 00288 for (IntRelTypes irts; irts(); ++irts) { 00289 (void) new IntInt("12",d1,a2,irts.irt()); 00290 (void) new IntInt("13",d1,a3,irts.irt()); 00291 (void) new IntInt("14",d1,a4,irts.irt()); 00292 (void) new IntInt("15",d1,a5,irts.irt()); 00293 (void) new IntInt("22",d2,a2,irts.irt()); 00294 (void) new IntInt("23",d2,a3,irts.irt()); 00295 (void) new IntInt("24",d2,a4,irts.irt()); 00296 (void) new IntInt("25",d2,a5,irts.irt()); 00297 if (i < 5) { 00298 (void) new IntVar("12",d1,a2,irts.irt()); 00299 (void) new IntVar("13",d1,a3,irts.irt()); 00300 (void) new IntVar("14",d1,a4,irts.irt()); 00301 (void) new IntVar("15",d1,a5,irts.irt()); 00302 (void) new IntVar("22",d2,a2,irts.irt()); 00303 (void) new IntVar("23",d2,a3,irts.irt()); 00304 (void) new IntVar("24",d2,a4,irts.irt()); 00305 (void) new IntVar("25",d2,a5,irts.irt()); 00306 } 00307 } 00308 (void) new IntInt("12",d1,a2,IRT_EQ,ICL_DOM); 00309 (void) new IntInt("13",d1,a3,IRT_EQ,ICL_DOM); 00310 (void) new IntInt("14",d1,a4,IRT_EQ,ICL_DOM); 00311 (void) new IntInt("15",d1,a5,IRT_EQ,ICL_DOM); 00312 (void) new IntInt("22",d2,a2,IRT_EQ,ICL_DOM); 00313 (void) new IntInt("23",d2,a3,IRT_EQ,ICL_DOM); 00314 (void) new IntInt("24",d2,a4,IRT_EQ,ICL_DOM); 00315 (void) new IntInt("25",d2,a5,IRT_EQ,ICL_DOM); 00316 if (i < 4) { 00317 (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM); 00318 (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM); 00319 (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM); 00320 (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM); 00321 } 00322 } 00323 } 00324 { 00325 const int av1[10] = { 00326 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 00327 }; 00328 const int av2[10] = { 00329 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1 00330 }; 00331 00332 for (int i=1; i<=10; i += 3) { 00333 IntArgs a1(i, av1); 00334 IntArgs a2(i, av2); 00335 for (int c=0; c<=6; c++) 00336 for (IntRelTypes irts; irts(); ++irts) { 00337 (void) new BoolInt("1",a1,irts.irt(),c); 00338 (void) new BoolInt("2",a2,irts.irt(),-c); 00339 } 00340 } 00341 00342 IntArgs a3(5, 1,2,3,4,5); 00343 IntArgs a4(5, -1,-2,-3,-4,-5); 00344 IntArgs a5(5, -1,-2,1,2,4); 00345 00346 for (IntRelTypes irts; irts(); ++irts) { 00347 for (int c=0; c<=16; c++) { 00348 (void) new BoolInt("3",a3,irts.irt(),c); 00349 (void) new BoolInt("4",a4,irts.irt(),-c); 00350 (void) new BoolInt("5",a5,irts.irt(),c); 00351 (void) new BoolInt("6",a5,irts.irt(),-c); 00352 } 00353 } 00354 00355 for (int i=1; i<=5; i += 2) { 00356 IntArgs a1(i, av1); 00357 IntArgs a2(i, av2); 00358 for (IntRelTypes irts; irts(); ++irts) { 00359 (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt()); 00360 (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt()); 00361 } 00362 } 00363 00364 IntArgs a6(4, 1,2,3,4); 00365 IntArgs a7(4, -1,-2,-3,-4); 00366 IntArgs a8(4, -1,-2,1,2); 00367 IntArgs a9(6, -1,-2,1,2,-3,3); 00368 00369 for (IntRelTypes irts; irts(); ++irts) { 00370 (void) new BoolVar("6",0,10,a6,irts.irt()); 00371 (void) new BoolVar("7",-10,0,a7,irts.irt()); 00372 (void) new BoolVar("8",-3,3,a8,irts.irt()); 00373 (void) new BoolVar("9",-3,3,a9,irts.irt()); 00374 } 00375 00376 } 00377 } 00378 }; 00379 00380 Create c; 00382 00383 } 00384 }} 00385 00386 // STATISTICS: test-int