00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
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
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
00104 for (int i=0; i<t; i++)
00105 if (used[i] > c) {
00106 delete [] used;
00107 return false;
00108 }
00109
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
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
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
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
00188 for (int i=0; i<t; i++) {
00189 if (used[i] > c) {
00190 delete [] used;
00191 return false;
00192 }
00193 }
00194
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
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
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
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
00279 for (int i=0; i<t; i++)
00280 if (used[i] > c) {
00281 delete [] used;
00282 return false;
00283 }
00284
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
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
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
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
00374 for (int i=0; i<t; i++)
00375 if (used[i] > c) {
00376 delete [] used;
00377 return false;
00378 }
00379
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
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