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