cumulative.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, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-08 13:04:57 +0200 (Tue, 08 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11058 $ 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 #include <gecode/scheduling.hh> 00042 00043 namespace Test { namespace Int { 00044 00046 namespace Cumulative { 00047 00053 00054 class ManFixPCumulative : public Test { 00055 protected: 00057 int c; 00059 Gecode::IntArgs p; 00061 Gecode::IntArgs u; 00063 static int st(int c, 00064 const Gecode::IntArgs& p, const Gecode::IntArgs& u) { 00065 double e = 0; 00066 for (int i=p.size(); i--; ) 00067 e += static_cast<double>(p[i])*u[i]; 00068 return e / c; 00069 } 00071 int o; 00072 public: 00074 ManFixPCumulative(int c0, 00075 const Gecode::IntArgs& p0, 00076 const Gecode::IntArgs& u0, 00077 int o0) 00078 : Test("Scheduling::Cumulative::Man::Fix::"+str(o0)+"::"+ 00079 str(c0)+"::"+str(p0)+"::"+str(u0), 00080 p0.size(),o0,o0+st(c0,p0,u0)), 00081 c(c0), p(p0), u(u0), o(o0) { 00082 testsearch = false; 00083 testfix = false; 00084 contest = CTL_NONE; 00085 } 00087 virtual Assignment* assignment(void) const { 00088 return new RandomAssignment(arity,dom,500); 00089 } 00091 virtual bool solution(const Assignment& x) const { 00092 // Compute maximal time 00093 int t = 0; 00094 for (int i=0; i<x.size(); i++) 00095 t = std::max(t,x[i]-o+std::max(1,p[i])); 00096 // Compute resource usage (including at start times) 00097 int* used = new int[t]; 00098 for (int i=0; i<t; i++) 00099 used[i] = 0; 00100 for (int i=0; i<x.size(); i++) 00101 for (int t=0; t<p[i]; t++) 00102 used[x[i]-o+t] += u[i]; 00103 // Check resource usage 00104 for (int i=0; i<t; i++) 00105 if (used[i] > c) { 00106 delete [] used; 00107 return false; 00108 } 00109 // Compute resource usage (only internal) 00110 for (int i=0; i<t; i++) 00111 used[i] = 0; 00112 for (int i=0; i<x.size(); i++) { 00113 for (int t=1; t<p[i]; t++) { 00114 used[x[i]-o+t] += u[i]; 00115 } 00116 } 00117 // Check resource usage at start times 00118 for (int i=0; i<x.size(); i++) 00119 if (used[x[i]-o]+u[i] > c) { 00120 delete [] used; 00121 return false; 00122 } 00123 delete [] used; 00124 return true; 00125 } 00127 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00128 Gecode::cumulative(home, c, x, p, u); 00129 } 00130 }; 00131 00132 00134 class OptFixPCumulative : public Test { 00135 protected: 00137 int c; 00139 Gecode::IntArgs p; 00141 Gecode::IntArgs u; 00143 int l; 00145 int o; 00147 static int st(int c, 00148 const Gecode::IntArgs& p, const Gecode::IntArgs& u) { 00149 double e = 0; 00150 for (int i=p.size(); i--; ) 00151 e += static_cast<double>(p[i])*u[i]; 00152 return e / c; 00153 } 00154 public: 00156 OptFixPCumulative(int c0, 00157 const Gecode::IntArgs& p0, 00158 const Gecode::IntArgs& u0, 00159 int o0) 00160 : Test("Scheduling::Cumulative::Opt::Fix::"+str(o0)+"::"+ 00161 str(c0)+"::"+str(p0)+"::"+str(u0), 00162 2*p0.size(),o0,o0+st(c0,p0,u0)), 00163 c(c0), p(p0), u(u0), l(o0+st(c,p,u)/2), o(o0) { 00164 testsearch = false; 00165 testfix = false; 00166 contest = CTL_NONE; 00167 } 00169 virtual Assignment* assignment(void) const { 00170 return new RandomAssignment(arity,dom,500); 00171 } 00173 virtual bool solution(const Assignment& x) const { 00174 int n = x.size() / 2; 00175 // Compute maximal time 00176 int t = 0; 00177 for (int i=0; i<n; i++) 00178 t = std::max(t,x[i]-o+std::max(1,p[i])); 00179 // Compute resource usage (including at start times) 00180 int* used = new int[t]; 00181 for (int i=0; i<t; i++) 00182 used[i] = 0; 00183 for (int i=0; i<n; i++) 00184 if (x[n+i] > l) 00185 for (int t=0; t<p[i]; t++) 00186 used[x[i]-o+t] += u[i]; 00187 // Check resource usage 00188 for (int i=0; i<t; i++) { 00189 if (used[i] > c) { 00190 delete [] used; 00191 return false; 00192 } 00193 } 00194 // Compute resource usage (only internal) 00195 for (int i=0; i<t; i++) 00196 used[i] = 0; 00197 for (int i=0; i<n; i++) 00198 if (x[n+i] > l) { 00199 for (int t=1; t<p[i]; t++) 00200 used[x[i]-o+t] += u[i]; 00201 } 00202 // Check resource usage at start times 00203 for (int i=0; i<n; i++) 00204 if (x[n+i] > l) 00205 if (used[x[i]-o]+u[i] > c) { 00206 delete [] used; 00207 return false; 00208 } 00209 delete [] used; 00210 return true; 00211 } 00213 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00214 int n=x.size() / 2; 00215 Gecode::IntVarArgs s(n); 00216 Gecode::BoolVarArgs m(n); 00217 for (int i=0; i<n; i++) { 00218 s[i]=x[i]; 00219 m[i]=Gecode::expr(home, x[n+i] > l); 00220 } 00221 Gecode::cumulative(home, c, s, p, u, m); 00222 } 00223 }; 00224 00226 class ManFlexCumulative : public Test { 00227 protected: 00229 int c; 00231 int _minP; 00233 int _maxP; 00235 Gecode::IntArgs u; 00237 static int st(int c, int maxP, const Gecode::IntArgs& u) { 00238 double e = 0; 00239 for (int i=u.size(); i--; ) 00240 e += static_cast<double>(maxP)*u[i]; 00241 return e / c; 00242 } 00244 int o; 00245 public: 00247 ManFlexCumulative(int c0, int minP, int maxP, 00248 const Gecode::IntArgs& u0, 00249 int o0) 00250 : Test("Scheduling::Cumulative::Man::Flex::"+str(o0)+"::"+ 00251 str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0), 00252 2*u0.size(),0,std::max(maxP,st(c0,maxP,u0))), 00253 c(c0), _minP(minP), _maxP(maxP), u(u0), o(o0) { 00254 testsearch = false; 00255 testfix = false; 00256 contest = CTL_NONE; 00257 } 00259 virtual Assignment* assignment(void) const { 00260 return new RandomMixAssignment(arity/2,dom,arity/2, 00261 Gecode::IntSet(_minP,_maxP),500); 00262 } 00264 virtual bool solution(const Assignment& x) const { 00265 int n = x.size()/2; 00266 // Compute maximal time 00267 int t = 0; 00268 for (int i=0; i<n; i++) { 00269 t = std::max(t,x[i]+std::max(1,x[n+i])); 00270 } 00271 // Compute resource usage (including at start times) 00272 int* used = new int[t]; 00273 for (int i=0; i<t; i++) 00274 used[i] = 0; 00275 for (int i=0; i<n; i++) 00276 for (int t=0; t<x[n+i]; t++) 00277 used[x[i]+t] += u[i]; 00278 // Check resource usage 00279 for (int i=0; i<t; i++) 00280 if (used[i] > c) { 00281 delete [] used; 00282 return false; 00283 } 00284 // Compute resource usage (only internal) 00285 for (int i=0; i<t; i++) 00286 used[i] = 0; 00287 for (int i=0; i<n; i++) { 00288 for (int t=1; t<x[n+i]; t++) 00289 used[x[i]+t] += u[i]; 00290 } 00291 // Check resource usage at start times 00292 for (int i=0; i<n; i++) 00293 if (used[x[i]]+u[i] > c) { 00294 delete [] used; 00295 return false; 00296 } 00297 delete [] used; 00298 return true; 00299 } 00301 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00302 Gecode::IntVarArgs s(x.size()/2); 00303 Gecode::IntVarArgs px(x.slice(x.size()/2)); 00304 Gecode::IntVarArgs e(home,x.size()/2, 00305 Gecode::Int::Limits::min, 00306 Gecode::Int::Limits::max); 00307 for (int i=s.size(); i--;) { 00308 s[i] = expr(home, o+x[i]); 00309 rel(home, s[i]+px[i] == e[i]); 00310 rel(home, _minP <= px[i]); 00311 rel(home, _maxP >= px[i]); 00312 } 00313 Gecode::cumulative(home, c, s, px, e, u); 00314 } 00315 }; 00316 00318 class OptFlexCumulative : public Test { 00319 protected: 00321 int c; 00323 int _minP; 00325 int _maxP; 00327 Gecode::IntArgs u; 00329 int l; 00331 int o; 00333 static int st(int c, int maxP, const Gecode::IntArgs& u) { 00334 double e = 0; 00335 for (int i=u.size(); i--; ) 00336 e += static_cast<double>(maxP)*u[i]; 00337 return e / c; 00338 } 00339 public: 00341 OptFlexCumulative(int c0, int minP, int maxP, 00342 const Gecode::IntArgs& u0, 00343 int o0) 00344 : Test("Scheduling::Cumulative::Opt::Flex::"+str(o0)+"::"+ 00345 str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0), 00346 3*u0.size(),0,std::max(maxP,st(c0,maxP,u0))), 00347 c(c0), _minP(minP), _maxP(maxP), u(u0), 00348 l(std::max(maxP,st(c0,maxP,u0))/2), o(o0) { 00349 testsearch = false; 00350 testfix = false; 00351 contest = CTL_NONE; 00352 } 00354 virtual Assignment* assignment(void) const { 00355 return new RandomMixAssignment(2*(arity/3),dom,arity/3, 00356 Gecode::IntSet(_minP,_maxP),500); 00357 } 00359 virtual bool solution(const Assignment& x) const { 00360 int n = x.size() / 3; 00361 // Compute maximal time 00362 int t = 0; 00363 for (int i=0; i<n; i++) 00364 t = std::max(t,x[i]+std::max(1,x[2*n+i])); 00365 // Compute resource usage (including at start times) 00366 int* used = new int[t]; 00367 for (int i=0; i<t; i++) 00368 used[i] = 0; 00369 for (int i=0; i<n; i++) 00370 if (x[n+i] > l) 00371 for (int t=0; t<x[2*n+i]; t++) 00372 used[x[i]+t] += u[i]; 00373 // Check resource usage 00374 for (int i=0; i<t; i++) 00375 if (used[i] > c) { 00376 delete [] used; 00377 return false; 00378 } 00379 // Compute resource usage (only internal) 00380 for (int i=0; i<t; i++) 00381 used[i] = 0; 00382 for (int i=0; i<n; i++) 00383 if (x[n+i] > l) 00384 for (int t=1; t<x[2*n+i]; t++) 00385 used[x[i]+t] += u[i]; 00386 // Check resource usage at start times 00387 for (int i=0; i<n; i++) 00388 if (x[n+i] > l && used[x[i]]+u[i] > c) { 00389 delete [] used; 00390 return false; 00391 } 00392 delete [] used; 00393 return true; 00394 } 00396 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00397 int n=x.size() / 3; 00398 00399 Gecode::IntVarArgs s(n); 00400 Gecode::IntVarArgs px(n); 00401 Gecode::IntVarArgs e(home,n, 00402 Gecode::Int::Limits::min, 00403 Gecode::Int::Limits::max); 00404 for (int i=n; i--;) { 00405 s[i] = expr(home, o+x[i]); 00406 px[i] = x[2*n+i]; 00407 rel(home, s[i]+px[i] == e[i]); 00408 rel(home, _minP <= px[i]); 00409 rel(home, _maxP >= px[i]); 00410 } 00411 Gecode::BoolVarArgs m(n); 00412 for (int i=0; i<n; i++) 00413 m[i]=Gecode::expr(home, (x[n+i] > l)); 00414 Gecode::cumulative(home, c, s, px, e, u, m); 00415 } 00416 }; 00417 00419 class Create { 00420 public: 00422 Create(void) { 00423 using namespace Gecode; 00424 IntArgs p1(4, 1,1,1,1); 00425 IntArgs p2(4, 2,2,2,2); 00426 IntArgs p3(4, 4,3,3,5); 00427 IntArgs p4(4, 4,0,3,5); 00428 00429 IntArgs u1(4, 1,1,1,1); 00430 IntArgs u2(4, 2,2,2,2); 00431 IntArgs u3(4, 2,3,4,5); 00432 00433 for (int c=1; c<8; c++) { 00434 int off = 0; 00435 for (int coff=0; coff<2; coff++) { 00436 (void) new ManFixPCumulative(c,p1,u1,off); 00437 (void) new ManFixPCumulative(c,p1,u2,off); 00438 (void) new ManFixPCumulative(c,p1,u3,off); 00439 (void) new ManFixPCumulative(c,p2,u1,off); 00440 (void) new ManFixPCumulative(c,p2,u2,off); 00441 (void) new ManFixPCumulative(c,p2,u3,off); 00442 (void) new ManFixPCumulative(c,p3,u1,off); 00443 (void) new ManFixPCumulative(c,p3,u2,off); 00444 (void) new ManFixPCumulative(c,p3,u3,off); 00445 (void) new ManFixPCumulative(c,p4,u1,off); 00446 (void) new ManFixPCumulative(c,p4,u2,off); 00447 (void) new ManFixPCumulative(c,p4,u3,off); 00448 00449 (void) new ManFlexCumulative(c,0,1,u1,off); 00450 (void) new ManFlexCumulative(c,0,1,u2,off); 00451 (void) new ManFlexCumulative(c,0,1,u3,off); 00452 (void) new ManFlexCumulative(c,0,2,u1,off); 00453 (void) new ManFlexCumulative(c,0,2,u2,off); 00454 (void) new ManFlexCumulative(c,0,2,u3,off); 00455 (void) new ManFlexCumulative(c,3,5,u1,off); 00456 (void) new ManFlexCumulative(c,3,5,u2,off); 00457 (void) new ManFlexCumulative(c,3,5,u3,off); 00458 00459 (void) new OptFixPCumulative(c,p1,u1,off); 00460 (void) new OptFixPCumulative(c,p1,u2,off); 00461 (void) new OptFixPCumulative(c,p1,u3,off); 00462 (void) new OptFixPCumulative(c,p2,u1,off); 00463 (void) new OptFixPCumulative(c,p2,u2,off); 00464 (void) new OptFixPCumulative(c,p2,u3,off); 00465 (void) new OptFixPCumulative(c,p3,u1,off); 00466 (void) new OptFixPCumulative(c,p3,u2,off); 00467 (void) new OptFixPCumulative(c,p3,u3,off); 00468 (void) new OptFixPCumulative(c,p4,u1,off); 00469 (void) new OptFixPCumulative(c,p4,u2,off); 00470 (void) new OptFixPCumulative(c,p4,u3,off); 00471 00472 (void) new OptFlexCumulative(c,0,1,u1,off); 00473 (void) new OptFlexCumulative(c,0,1,u2,off); 00474 (void) new OptFlexCumulative(c,0,1,u3,off); 00475 (void) new OptFlexCumulative(c,0,2,u1,off); 00476 (void) new OptFlexCumulative(c,0,2,u2,off); 00477 (void) new OptFlexCumulative(c,0,2,u3,off); 00478 (void) new OptFlexCumulative(c,3,5,u1,off); 00479 (void) new OptFlexCumulative(c,3,5,u2,off); 00480 (void) new OptFlexCumulative(c,3,5,u3,off); 00481 00482 off = Gecode::Int::Limits::min; 00483 } 00484 } 00485 } 00486 }; 00487 00488 Create c; 00490 00491 } 00492 }} 00493 00494 // STATISTICS: test-int