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
00042 namespace Test { namespace Int {
00043
00045 namespace Cumulative {
00046
00052
00053 class ManFixPCumulative : public Test {
00054 protected:
00056 int c;
00058 Gecode::IntArgs p;
00060 Gecode::IntArgs u;
00062 static int st(int c,
00063 const Gecode::IntArgs& p, const Gecode::IntArgs& u) {
00064 double e = 0;
00065 for (int i=p.size(); i--; )
00066 e += static_cast<double>(p[i])*u[i];
00067 return e / std::max(1,std::abs(c));
00068 }
00070 int o;
00071 public:
00073 ManFixPCumulative(int c0,
00074 const Gecode::IntArgs& p0,
00075 const Gecode::IntArgs& u0,
00076 int o0,
00077 Gecode::IntPropLevel ipl0)
00078 : Test("Cumulative::Man::Fix::"+str(o0)+"::"+
00079 str(c0)+"::"+str(p0)+"::"+str(u0)+"::"+str(ipl0),
00080 (c0 >= 0) ? p0.size():p0.size()+1,0,st(c0,p0,u0),false,ipl0),
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 int cmax = (c >= 0) ? c : x[x.size()-1];
00093 int n = (c >= 0) ? x.size() : x.size()-1;
00094
00095 if (c < 0 && x[n] > -c)
00096 return false;
00097
00098
00099 int t = 0;
00100 for (int i=0; i<n; i++)
00101 t = std::max(t,x[i]+std::max(1,p[i]));
00102
00103 int* used = new int[t];
00104 for (int i=0; i<t; i++)
00105 used[i] = 0;
00106 for (int i=0; i<n; i++)
00107 for (int t=0; t<p[i]; t++)
00108 used[x[i]+t] += u[i];
00109
00110 for (int i=0; i<t; i++)
00111 if (used[i] > cmax) {
00112 delete [] used;
00113 return false;
00114 }
00115
00116 for (int i=0; i<t; i++)
00117 used[i] = 0;
00118 for (int i=0; i<n; i++) {
00119 for (int t=1; t<p[i]; t++) {
00120 used[x[i]+t] += u[i];
00121 }
00122 }
00123
00124 for (int i=0; i<n; i++)
00125 if (used[x[i]]+u[i] > cmax) {
00126 delete [] used;
00127 return false;
00128 }
00129 delete [] used;
00130 return true;
00131 }
00133 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00134 int n = (c >= 0) ? x.size() : x.size()-1;
00135 Gecode::IntVarArgs xx;
00136 if (o==0) {
00137 xx=x.slice(0,1,n);
00138 } else {
00139 xx=Gecode::IntVarArgs(n);
00140 for (int i=n; i--;)
00141 xx[i]=Gecode::expr(home,x[i]+o,Gecode::IPL_DOM);
00142 }
00143 if (c >= 0) {
00144 Gecode::cumulative(home, c, xx, p, u, ipl);
00145 } else {
00146 Gecode::rel(home, x[n] <= -c);
00147 Gecode::cumulative(home, x[n], xx, p, u, ipl);
00148 }
00149 }
00150 };
00151
00152
00154 class OptFixPCumulative : public Test {
00155 protected:
00157 int c;
00159 Gecode::IntArgs p;
00161 Gecode::IntArgs u;
00163 int l;
00165 int o;
00167 static int st(int c,
00168 const Gecode::IntArgs& p, const Gecode::IntArgs& u) {
00169 double e = 0;
00170 for (int i=p.size(); i--; )
00171 e += static_cast<double>(p[i])*u[i];
00172 return e / std::max(1,std::abs(c));
00173 }
00174 public:
00176 OptFixPCumulative(int c0,
00177 const Gecode::IntArgs& p0,
00178 const Gecode::IntArgs& u0,
00179 int o0,
00180 Gecode::IntPropLevel ipl0)
00181 : Test("Cumulative::Opt::Fix::"+str(o0)+"::"+
00182 str(c0)+"::"+str(p0)+"::"+str(u0)+"::"+str(ipl0),
00183 (c0 >= 0) ? 2*p0.size() : 2*p0.size()+1,0,st(c0,p0,u0),
00184 false,ipl0),
00185 c(c0), p(p0), u(u0), l(st(c,p,u)/2), o(o0) {
00186 testsearch = false;
00187 testfix = false;
00188 contest = CTL_NONE;
00189 }
00191 virtual Assignment* assignment(void) const {
00192 return new RandomAssignment(arity,dom,500);
00193 }
00195 virtual bool solution(const Assignment& x) const {
00196 int nn = (c >= 0) ? x.size() : x.size()-1;
00197 int cmax = (c >= 0) ? c : x[nn];
00198
00199 if (c < 0 && x[nn] > -c)
00200 return false;
00201
00202 int n = nn / 2;
00203
00204 int t = 0;
00205 for (int i=0; i<n; i++)
00206 t = std::max(t,x[i]+std::max(1,p[i]));
00207
00208 int* used = new int[t];
00209 for (int i=0; i<t; i++)
00210 used[i] = 0;
00211 for (int i=0; i<n; i++)
00212 if (x[n+i] > l)
00213 for (int t=0; t<p[i]; t++)
00214 used[x[i]+t] += u[i];
00215
00216 for (int i=0; i<t; i++) {
00217 if (used[i] > cmax) {
00218 delete [] used;
00219 return false;
00220 }
00221 }
00222
00223 for (int i=0; i<t; i++)
00224 used[i] = 0;
00225 for (int i=0; i<n; i++)
00226 if (x[n+i] > l) {
00227 for (int t=1; t<p[i]; t++)
00228 used[x[i]+t] += u[i];
00229 }
00230
00231 for (int i=0; i<n; i++)
00232 if (x[n+i] > l)
00233 if (used[x[i]]+u[i] > cmax) {
00234 delete [] used;
00235 return false;
00236 }
00237 delete [] used;
00238 return true;
00239 }
00241 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00242 int nn=(c >= 0) ? x.size() : x.size()-1;
00243 int n=nn / 2;
00244 Gecode::IntVarArgs s(n);
00245 Gecode::BoolVarArgs m(n);
00246
00247 for (int i=0; i<n; i++) {
00248 s[i]=(c >= 0) ? x[i] : Gecode::expr(home,x[i]+o,Gecode::IPL_DOM);
00249 m[i]=Gecode::expr(home, x[n+i] > l);
00250 }
00251
00252 if (c >= 0) {
00253 Gecode::cumulative(home, c, s, p, u, m, ipl);
00254 } else {
00255 Gecode::rel(home, x[nn] <= -c);
00256 Gecode::cumulative(home, x[nn], s, p, u, m, ipl);
00257 }
00258 }
00259 };
00260
00262 class ManFlexCumulative : public Test {
00263 protected:
00265 int c;
00267 int _minP;
00269 int _maxP;
00271 Gecode::IntArgs u;
00273 static int st(int c, int maxP, const Gecode::IntArgs& u) {
00274 double e = 0;
00275 for (int i=u.size(); i--; )
00276 e += static_cast<double>(maxP)*u[i];
00277 return e / std::max(1,std::abs(c));
00278 }
00280 int o;
00281 public:
00283 ManFlexCumulative(int c0, int minP, int maxP,
00284 const Gecode::IntArgs& u0,
00285 int o0,
00286 Gecode::IntPropLevel ipl0)
00287 : Test("Cumulative::Man::Flex::"+str(o0)+"::"+
00288 str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0)+
00289 "::"+str(ipl0),
00290 (c0 >= 0) ? 2*u0.size() : 2*u0.size()+1,
00291 0,std::max(maxP,st(c0,maxP,u0)),false,ipl0),
00292 c(c0), _minP(minP), _maxP(maxP), u(u0), o(o0) {
00293 testsearch = false;
00294 testfix = false;
00295 contest = CTL_NONE;
00296 }
00298 virtual Assignment* assignment(void) const {
00299 return new RandomMixAssignment((c >= 0) ? arity/2 : arity/2+1,
00300 dom,arity/2,
00301 Gecode::IntSet(_minP,_maxP),500);
00302 }
00304 virtual bool solution(const Assignment& x) const {
00305 int nn = (c >= 0) ? x.size() : x.size()-1;
00306 int n = nn/2;
00307 int cmax = (c >= 0) ? c : x[n];
00308 int pstart = (c >= 0) ? n : n+1;
00309
00310 if (c < 0 && cmax > -c)
00311 return false;
00312
00313
00314 int t = 0;
00315 for (int i=0; i<n; i++) {
00316 t = std::max(t,x[i]+std::max(1,x[pstart+i]));
00317 }
00318
00319 int* used = new int[t];
00320 for (int i=0; i<t; i++)
00321 used[i] = 0;
00322 for (int i=0; i<n; i++)
00323 for (int t=0; t<x[pstart+i]; t++)
00324 used[x[i]+t] += u[i];
00325
00326 for (int i=0; i<t; i++)
00327 if (used[i] > cmax) {
00328 delete [] used;
00329 return false;
00330 }
00331
00332 for (int i=0; i<t; i++)
00333 used[i] = 0;
00334 for (int i=0; i<n; i++) {
00335 for (int t=1; t<x[pstart+i]; t++)
00336 used[x[i]+t] += u[i];
00337 }
00338
00339 for (int i=0; i<n; i++)
00340 if (used[x[i]]+u[i] > cmax) {
00341 delete [] used;
00342 return false;
00343 }
00344 delete [] used;
00345 return true;
00346 }
00348 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00349 int nn = (c >= 0) ? x.size() : x.size()-1;
00350 int n = nn/2;
00351 int pstart = (c >= 0) ? n : n+1;
00352 Gecode::IntVarArgs s(n);
00353 Gecode::IntVarArgs px(x.slice(pstart,1,n));
00354 Gecode::IntVarArgs e(home,n,
00355 Gecode::Int::Limits::min,
00356 Gecode::Int::Limits::max);
00357 for (int i=s.size(); i--;) {
00358 s[i] = expr(home, o+x[i], Gecode::IPL_DOM);
00359 rel(home, s[i]+px[i] == e[i]);
00360 rel(home, _minP <= px[i]);
00361 rel(home, _maxP >= px[i]);
00362 }
00363 if (c >= 0) {
00364 Gecode::cumulative(home, c, s, px, e, u, ipl);
00365 } else {
00366 rel(home, x[n] <= -c);
00367 Gecode::cumulative(home, x[n], s, px, e, u, ipl);
00368 }
00369 }
00370 };
00371
00373 class OptFlexCumulative : public Test {
00374 protected:
00376 int c;
00378 int _minP;
00380 int _maxP;
00382 Gecode::IntArgs u;
00384 int l;
00386 int o;
00388 static int st(int c, int maxP, const Gecode::IntArgs& u) {
00389 double e = 0;
00390 for (int i=u.size(); i--; )
00391 e += static_cast<double>(maxP)*u[i];
00392 return e / std::max(1,std::abs(c));
00393 }
00394 public:
00396 OptFlexCumulative(int c0, int minP, int maxP,
00397 const Gecode::IntArgs& u0,
00398 int o0,
00399 Gecode::IntPropLevel ipl0)
00400 : Test("Cumulative::Opt::Flex::"+str(o0)+"::"+
00401 str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0)+
00402 "::"+str(ipl0),
00403 (c0 >= 0) ? 3*u0.size() : 3*u0.size()+1,
00404 0,std::max(maxP,st(c0,maxP,u0)), false,ipl0),
00405 c(c0), _minP(minP), _maxP(maxP), u(u0),
00406 l(std::max(maxP,st(c0,maxP,u0))/2), o(o0) {
00407 testsearch = false;
00408 testfix = false;
00409 contest = CTL_NONE;
00410 }
00412 virtual Assignment* assignment(void) const {
00413 return new RandomMixAssignment((c >= 0) ? 2*(arity/3) : 2*(arity/3)+1,
00414 dom,arity/3,
00415 Gecode::IntSet(_minP,_maxP),500);
00416 }
00418 virtual bool solution(const Assignment& x) const {
00419 int nn = (c >= 0) ? x.size() : x.size()-1;
00420 int n = nn / 3;
00421 int cmax = (c >= 0) ? c : x[2*n];
00422 int pstart = (c >= 0) ? 2*n : 2*n+1;
00423
00424 if (c < 0 && cmax > -c)
00425 return false;
00426
00427
00428 int t = 0;
00429 for (int i=0; i<n; i++)
00430 t = std::max(t,x[i]+std::max(1,x[pstart+i]));
00431
00432 int* used = new int[t];
00433 for (int i=0; i<t; i++)
00434 used[i] = 0;
00435 for (int i=0; i<n; i++)
00436 if (x[n+i] > l)
00437 for (int t=0; t<x[pstart+i]; t++)
00438 used[x[i]+t] += u[i];
00439
00440 for (int i=0; i<t; i++)
00441 if (used[i] > cmax) {
00442 delete [] used;
00443 return false;
00444 }
00445
00446 for (int i=0; i<t; i++)
00447 used[i] = 0;
00448 for (int i=0; i<n; i++)
00449 if (x[n+i] > l)
00450 for (int t=1; t<x[pstart+i]; t++)
00451 used[x[i]+t] += u[i];
00452
00453 for (int i=0; i<n; i++)
00454 if (x[n+i] > l && used[x[i]]+u[i] > cmax) {
00455 delete [] used;
00456 return false;
00457 }
00458 delete [] used;
00459 return true;
00460 }
00462 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00463 int nn = (c >= 0) ? x.size() : x.size()-1;
00464 int n=nn / 3;
00465 int pstart= (c >= 0) ? 2*n : 2*n+1;
00466
00467 Gecode::IntVarArgs s(n);
00468 Gecode::IntVarArgs px(n);
00469 Gecode::IntVarArgs e(home,n,
00470 Gecode::Int::Limits::min,
00471 Gecode::Int::Limits::max);
00472 for (int i=n; i--;) {
00473 s[i] = expr(home, o+x[i]);
00474 px[i] = x[pstart+i];
00475 rel(home, s[i]+px[i] == e[i]);
00476 rel(home, _minP <= px[i]);
00477 rel(home, _maxP >= px[i]);
00478 }
00479 Gecode::BoolVarArgs m(n);
00480 for (int i=0; i<n; i++)
00481 m[i]=Gecode::expr(home, (x[n+i] > l));
00482 if (c >= 0) {
00483 Gecode::cumulative(home, c, s, px, e, u, m, ipl);
00484 } else {
00485 Gecode::rel(home, x[2*n] <= -c);
00486 Gecode::cumulative(home, x[2*n], s, px, e, u, m, ipl);
00487 }
00488 }
00489 };
00490
00492 class Create {
00493 public:
00495 Create(void) {
00496 using namespace Gecode;
00497 IntArgs p1(4, 1,1,1,1);
00498 IntArgs p2(4, 2,2,2,2);
00499 IntArgs p3(4, 4,3,3,5);
00500 IntArgs p4(4, 4,0,3,5);
00501 IntArgs p5(3, 1,1,1);
00502
00503 IntArgs u1(4, 1,1,1,1);
00504 IntArgs u2(4, 2,2,2,2);
00505 IntArgs u3(4, 2,3,4,5);
00506 IntArgs u4(4, 2,3,0,5);
00507 IntArgs u5(3, 1,3,2);
00508
00509 for (IntPropBasicAdvanced ipba; ipba(); ++ipba) {
00510
00511 (void) new ManFixPCumulative(3,p5,u5,0,ipba.ipl());
00512
00513 for (int c=-7; c<8; c++) {
00514 int off = 0;
00515 for (int coff=0; coff<2; coff++) {
00516 (void) new ManFixPCumulative(c,p1,u1,off,ipba.ipl());
00517 (void) new ManFixPCumulative(c,p1,u2,off,ipba.ipl());
00518 (void) new ManFixPCumulative(c,p1,u3,off,ipba.ipl());
00519 (void) new ManFixPCumulative(c,p1,u4,off,ipba.ipl());
00520 (void) new ManFixPCumulative(c,p2,u1,off,ipba.ipl());
00521 (void) new ManFixPCumulative(c,p2,u2,off,ipba.ipl());
00522 (void) new ManFixPCumulative(c,p2,u3,off,ipba.ipl());
00523 (void) new ManFixPCumulative(c,p2,u4,off,ipba.ipl());
00524 (void) new ManFixPCumulative(c,p3,u1,off,ipba.ipl());
00525 (void) new ManFixPCumulative(c,p3,u2,off,ipba.ipl());
00526 (void) new ManFixPCumulative(c,p3,u3,off,ipba.ipl());
00527 (void) new ManFixPCumulative(c,p3,u4,off,ipba.ipl());
00528 (void) new ManFixPCumulative(c,p4,u1,off,ipba.ipl());
00529 (void) new ManFixPCumulative(c,p4,u2,off,ipba.ipl());
00530 (void) new ManFixPCumulative(c,p4,u3,off,ipba.ipl());
00531 (void) new ManFixPCumulative(c,p4,u4,off,ipba.ipl());
00532
00533 (void) new ManFlexCumulative(c,0,1,u1,off,ipba.ipl());
00534 (void) new ManFlexCumulative(c,0,1,u2,off,ipba.ipl());
00535 (void) new ManFlexCumulative(c,0,1,u3,off,ipba.ipl());
00536 (void) new ManFlexCumulative(c,0,1,u4,off,ipba.ipl());
00537 (void) new ManFlexCumulative(c,0,2,u1,off,ipba.ipl());
00538 (void) new ManFlexCumulative(c,0,2,u2,off,ipba.ipl());
00539 (void) new ManFlexCumulative(c,0,2,u3,off,ipba.ipl());
00540 (void) new ManFlexCumulative(c,0,2,u4,off,ipba.ipl());
00541 (void) new ManFlexCumulative(c,3,5,u1,off,ipba.ipl());
00542 (void) new ManFlexCumulative(c,3,5,u2,off,ipba.ipl());
00543 (void) new ManFlexCumulative(c,3,5,u3,off,ipba.ipl());
00544 (void) new ManFlexCumulative(c,3,5,u4,off,ipba.ipl());
00545
00546 (void) new OptFixPCumulative(c,p1,u1,off,ipba.ipl());
00547 (void) new OptFixPCumulative(c,p1,u2,off,ipba.ipl());
00548 (void) new OptFixPCumulative(c,p1,u3,off,ipba.ipl());
00549 (void) new OptFixPCumulative(c,p1,u4,off,ipba.ipl());
00550 (void) new OptFixPCumulative(c,p2,u1,off,ipba.ipl());
00551 (void) new OptFixPCumulative(c,p2,u2,off,ipba.ipl());
00552 (void) new OptFixPCumulative(c,p2,u3,off,ipba.ipl());
00553 (void) new OptFixPCumulative(c,p2,u4,off,ipba.ipl());
00554 (void) new OptFixPCumulative(c,p3,u1,off,ipba.ipl());
00555 (void) new OptFixPCumulative(c,p3,u2,off,ipba.ipl());
00556 (void) new OptFixPCumulative(c,p3,u3,off,ipba.ipl());
00557 (void) new OptFixPCumulative(c,p3,u4,off,ipba.ipl());
00558 (void) new OptFixPCumulative(c,p4,u1,off,ipba.ipl());
00559 (void) new OptFixPCumulative(c,p4,u2,off,ipba.ipl());
00560 (void) new OptFixPCumulative(c,p4,u3,off,ipba.ipl());
00561 (void) new OptFixPCumulative(c,p4,u4,off,ipba.ipl());
00562
00563 (void) new OptFlexCumulative(c,0,1,u1,off,ipba.ipl());
00564 (void) new OptFlexCumulative(c,0,1,u2,off,ipba.ipl());
00565 (void) new OptFlexCumulative(c,0,1,u3,off,ipba.ipl());
00566 (void) new OptFlexCumulative(c,0,1,u4,off,ipba.ipl());
00567 (void) new OptFlexCumulative(c,0,2,u1,off,ipba.ipl());
00568 (void) new OptFlexCumulative(c,0,2,u2,off,ipba.ipl());
00569 (void) new OptFlexCumulative(c,0,2,u3,off,ipba.ipl());
00570 (void) new OptFlexCumulative(c,0,2,u4,off,ipba.ipl());
00571 (void) new OptFlexCumulative(c,3,5,u1,off,ipba.ipl());
00572 (void) new OptFlexCumulative(c,3,5,u2,off,ipba.ipl());
00573 (void) new OptFlexCumulative(c,3,5,u3,off,ipba.ipl());
00574 (void) new OptFlexCumulative(c,3,5,u4,off,ipba.ipl());
00575
00576 off = Gecode::Int::Limits::min;
00577 }
00578 }
00579 }
00580 }
00581 };
00582
00583 Create c;
00585
00586 }
00587 }}
00588
00589