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 <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 #include <iomanip>
00043
00044 using namespace Gecode;
00045
00046
00047 namespace {
00048
00049 extern const int* problems[];
00050
00051 extern const unsigned int n_problems;
00052 }
00053
00054 namespace {
00060 class CarOptions : public SizeOptions {
00061 private:
00063 Driver::UnsignedIntOption _maxstall;
00064
00065 public:
00067 CarOptions(const char* s)
00068 : SizeOptions(s),
00069 _maxstall("-maxstall", "Maximum numbere of stalls", 30)
00070 {
00071
00072 add(_maxstall);
00073 }
00075 void parse(int& argc, char* argv[]) {
00076 SizeOptions::parse(argc,argv);
00077 }
00079 int maxstall(void) const { return _maxstall.value(); }
00080 };
00081
00082
00100 template <class View>
00101 class PushToEnd : public NaryOnePropagator<View,Int::PC_INT_BND> {
00102 protected:
00103 using NaryOnePropagator<View,Int::PC_INT_BND>::x;
00104 using NaryOnePropagator<View,Int::PC_INT_BND>::y;
00105 int val;
00106
00108 PushToEnd(Space& home, bool share, PushToEnd& p);
00110 PushToEnd(Space& home, ViewArray<View>& x0, View y0, int val0);
00111 public:
00113 PushToEnd(Space& home, bool share, Propagator& p,
00114 ViewArray<View>& x0, View y0, int val0);
00116 virtual Actor* copy(Space& home, bool share);
00118 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00120 static ExecStatus post(Space& home,
00121 ViewArray<View>& x0, View y0, int val0);
00122 };
00123
00124 template <class View>
00125 inline
00126 PushToEnd<View>::PushToEnd(Space& home,
00127 ViewArray<View>& x0, View y0, int val0)
00128 : NaryOnePropagator<View,Int::PC_INT_BND>(home,x0,y0), val(val0) {}
00129
00130 template <class View>
00131 ExecStatus
00132 PushToEnd<View>::post(Space& home,
00133 ViewArray<View>& x0, View y0, int val0) {
00134 (void) new (home) PushToEnd<View>(home,x0,y0,val0);
00135 return ES_OK;
00136 }
00137
00138 template <class View>
00139 inline
00140 PushToEnd<View>::PushToEnd(Space& home, bool share, PushToEnd<View>& p)
00141 : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p), val(p.val) {}
00142
00143 template <class View>
00144 inline
00145 PushToEnd<View>::PushToEnd(Space& home, bool share, Propagator& p,
00146 ViewArray<View>& x0, View y0, int val0)
00147 : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p,x0,y0), val(val0) {}
00148
00149 template <class View>
00150 Actor*
00151 PushToEnd<View>::copy(Space& home, bool share) {
00152 return new (home) PushToEnd<View>(home,share,*this);
00153 }
00154
00155 template <class View>
00156 ExecStatus
00157 PushToEnd<View>::propagate(Space& home, const ModEventDelta&) {
00158
00159 int min = 0;
00160 for (int i = x.size(); i-- && x[i].min() >= val-1; ) {
00161 ++min;
00162 }
00163
00164 int max = 0;
00165 {
00166 int i = x.size();
00167 while (i--) {
00168 if (x[i].max() != val) break;
00169 ++max;
00170 if (max >= y.max()) break;
00171 }
00172
00173 while (i--) {
00174 GECODE_ME_CHECK(x[i].le(home, val));
00175 }
00176 }
00177
00178
00179 GECODE_ME_CHECK(y.gq(home, min));
00180 GECODE_ME_CHECK(y.lq(home, max));
00181
00182
00183 for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
00184 GECODE_ME_CHECK(x[pos].eq(home, val));
00185 }
00186
00187 return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00188 }
00189
00192 void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
00193 ViewArray<Int::IntView> vx(home, x);
00194 Int::IntView vy(y);
00195 GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
00196 }
00197
00198 }
00199
00200
00212 class CarSequencing : public Script {
00213 public:
00215 enum {
00216 BRANCH_INORDER,
00217 BRANCH_MIDDLE
00218 };
00220 enum {
00221 PROP_REGULAR,
00222 PROP_CUSTOM
00223 };
00224 protected:
00226 const int problem;
00228 const int ncars;
00230 const int noptions;
00232 const int nclasses;
00234 const int maxstall;
00236 const int stallval;
00238 const int endval;
00240 IntVar nstall;
00242 IntVar nend;
00244 IntVarArray s;
00245 public:
00247 CarSequencing(const CarOptions& opt)
00248 : problem(opt.size()),
00249 ncars(problems[problem][0]),
00250 noptions(problems[problem][1]),
00251 nclasses(problems[problem][2]),
00252 maxstall(opt.maxstall()),
00253 stallval(nclasses),
00254 endval(nclasses+1),
00255 nstall(*this, 0, maxstall),
00256 nend(*this, 0, maxstall),
00257 s(*this, ncars+maxstall, 0, nclasses+1)
00258 {
00259
00260 const int* probit = problems[problem] + 3;
00261
00262
00263 IntArgs max(noptions), block(noptions);
00264 for (int i = 0; i < noptions; ++i ) {
00265 max[i] = *probit++;
00266 }
00267 for (int i = 0; i < noptions; ++i ) {
00268 block[i] = *probit++;
00269 }
00270
00271 IntArgs ncc(nclasses);
00272
00273 IntSetArgs classes(noptions);
00274 int** cdata = new int*[noptions];
00275 for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00276 int* n = new int[noptions];
00277 for (int i = noptions; i--; ) n[i] = 0;
00278
00279 for (int c = 0; c < nclasses; ++c) {
00280 probit++;
00281 ncc[c] = *probit++;
00282 for (int o = 0; o < noptions; ++o) {
00283 if (*probit++) {
00284 cdata[o][n[o]++] = c;
00285 }
00286 }
00287 }
00288
00289 for (int o = noptions; o--; ) {
00290 classes[o] = IntSet(cdata[o], n[o]);
00291 delete [] cdata[o];
00292 }
00293 delete [] cdata;
00294 delete [] n;
00295
00296
00297 {
00298 IntSetArgs c(nclasses+2);
00299 for (int i = nclasses; i--; ) {
00300 c[i] = IntSet(ncc[i], ncc[i]);
00301 }
00302 c[stallval] = IntSet(0, maxstall);
00303 c[ endval] = IntSet(0, maxstall);
00304 count(*this, s, c);
00305 }
00306
00307
00308 count(*this, s, stallval, IRT_EQ, nstall);
00309 count(*this, s, endval, IRT_EQ, nend);
00310 rel(*this, nstall+nend == maxstall);
00311
00312
00313 IntSet one(1, 1);
00314 for (int o = noptions; o--; ) {
00315
00316 BoolVarArgs sb(s.size());
00317 for (int i = s.size(); i--; ) {
00318 BoolVar b(*this, 0, 1);
00319 dom(*this, s[i], classes[o], b);
00320 sb[i] = b;
00321 }
00322 sequence(*this, sb, one, block[o], 0, max[o]);
00323 }
00324
00325
00326 switch (opt.propagation()) {
00327 case PROP_REGULAR: {
00328 IntArgs notend(nclasses), notstallend(nclasses+1);
00329 for (int i = nclasses; i--; ) {
00330 notend[i] = i;
00331 notstallend[i] = i;
00332 }
00333 notstallend[nclasses] = stallval;
00334 REG r = *REG(notend) + REG(notstallend) + *REG(endval);
00335 extensional(*this, s, r);
00336 for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
00337 rel(*this, (nend > i) >> (s[pos]==endval));
00338 }
00339 } break;
00340 case PROP_CUSTOM: {
00341 pushtoend(*this, s, nend, endval);
00342 } break;
00343 }
00344
00345
00346
00347 switch (opt.branching()) {
00348 case BRANCH_INORDER:
00349 branch(*this, s, INT_VAR_NONE(), INT_VAL_MIN());
00350 break;
00351 case BRANCH_MIDDLE: {
00352 IntVarArgs m(s.size());
00353 int mid = s.size() / 2;
00354 int pos = 0;
00355 m[pos++] = s[mid];
00356 for (int i = 1; i <= m.size()/2; ++i) {
00357 if (mid-i >= 0)
00358 m[pos++] = s[mid-i];
00359 if (mid+i < s.size())
00360 m[pos++] = s[mid+i];
00361 }
00362 assert(pos == m.size());
00363 branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
00364 break;
00365 }
00366 }
00367 }
00368
00370 virtual void constrain(const Space& _best) {
00371 const CarSequencing& best = static_cast<const CarSequencing&>(_best);
00372 rel(*this, nstall, IRT_LE, best.nstall.val());
00373 }
00374
00376 virtual void
00377 print(std::ostream& os) const {
00378 int width = nclasses > 9 ? 2 : 1;
00379 const char* space = nclasses > 9 ? " " : "";
00380 os << "Stall slots=" << nstall
00381 << ", End slots=" << nend << std::endl;
00382 int i = 0;
00383 for (; i < s.size(); ++i) {
00384 if (s[i].assigned()) {
00385 int v = s[i].val();
00386 if (v == endval) break;
00387 if (v == stallval) os << space << "_ ";
00388 else os << std::setw(width) << v << " ";
00389 } else {
00390 os << space << "? ";
00391 }
00392 if ((i+1)%20 == 0) os << std::endl;
00393 }
00394 if (i%20)
00395 os << std::endl;
00396 os << std::endl;
00397 }
00398
00400 CarSequencing(bool share, CarSequencing& cs)
00401 : Script(share,cs),
00402 problem(cs.problem),
00403 ncars(cs.ncars),
00404 noptions(cs.noptions),
00405 nclasses(cs.nclasses),
00406 maxstall(cs.maxstall),
00407 stallval(cs.stallval),
00408 endval(cs.endval)
00409 {
00410 nstall.update(*this, share, cs.nstall);
00411 nend.update(*this, share, cs.nend);
00412 s.update(*this, share, cs.s);
00413 }
00415 virtual Space*
00416 copy(bool share) {
00417 return new CarSequencing(share,*this);
00418 }
00419 };
00420
00424 int
00425 main(int argc, char* argv[]) {
00426 CarOptions opt("CarSequencing");
00427 opt.solutions(0);
00428 opt.size(0);
00429 opt.branching(CarSequencing::BRANCH_INORDER);
00430 opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
00431 opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00432 opt.propagation(CarSequencing::PROP_CUSTOM);
00433 opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00434 opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
00435 opt.parse(argc,argv);
00436 if (opt.size() >= n_problems) {
00437 std::cerr << "Error: size must be between 0 and "
00438 << n_problems-1 << std::endl;
00439 return 1;
00440 }
00441
00442 Script::run<CarSequencing,BAB,CarOptions>(opt);
00443 return 0;
00444 }
00445
00446
00447 namespace {
00449
00451 const int p0[] = {
00452 10, 5, 6,
00453 1, 2, 1, 2, 1,
00454 2, 3, 3, 5, 5,
00455 0, 1, 1, 0, 1, 1, 0,
00456 1, 1, 0, 0, 0, 1, 0,
00457 2, 2, 0, 1, 0, 0, 1,
00458 3, 2, 0, 1, 0, 1, 0,
00459 4, 2, 1, 0, 1, 0, 0,
00460 5, 2, 1, 1, 0, 0, 0
00461 };
00462
00463
00464
00465
00466 const int p1[] = {
00467 100, 5, 22,
00468 1, 2, 1, 2, 1,
00469 2, 3, 3, 5, 5,
00470 0, 6, 1, 0, 0, 1, 0,
00471 1, 10, 1, 1, 1, 0, 0,
00472 2, 2, 1, 1, 0, 0, 1,
00473 3, 2, 0, 1, 1, 0, 0,
00474 4, 8, 0, 0, 0, 1, 0,
00475 5, 15, 0, 1, 0, 0, 0,
00476 6, 1, 0, 1, 1, 1, 0,
00477 7, 5, 0, 0, 1, 1, 0,
00478 8, 2, 1, 0, 1, 1, 0,
00479 9, 3, 0, 0, 1, 0, 0,
00480 10, 2, 1, 0, 1, 0, 0,
00481 11, 1, 1, 1, 1, 0, 1,
00482 12, 8, 0, 1, 0, 1, 0,
00483 13, 3, 1, 0, 0, 1, 1,
00484 14, 10, 1, 0, 0, 0, 0,
00485 15, 4, 0, 1, 0, 0, 1,
00486 16, 4, 0, 0, 0, 0, 1,
00487 17, 2, 1, 0, 0, 0, 1,
00488 18, 4, 1, 1, 0, 0, 0,
00489 19, 6, 1, 1, 0, 1, 0,
00490 20, 1, 1, 0, 1, 0, 1,
00491 21, 1, 1, 1, 1, 1, 1,
00492 };
00493
00494
00495
00496
00497 const int p2[] = {
00498 100, 5, 22,
00499 1, 2, 1, 2, 1,
00500 2, 3, 3, 5, 5,
00501 0, 13, 1, 0, 0, 0, 0,
00502 1, 8, 0, 0, 0, 1, 0,
00503 2, 7, 0, 1, 0, 0, 0,
00504 3, 1, 1, 0, 0, 1, 0,
00505 4, 12, 0, 0, 1, 0, 0,
00506 5, 5, 0, 1, 0, 1, 0,
00507 6, 5, 0, 0, 1, 1, 0,
00508 7, 6, 0, 1, 1, 0, 0,
00509 8, 3, 1, 0, 0, 0, 1,
00510 9, 12, 1, 1, 0, 0, 0,
00511 10, 8, 1, 1, 0, 1, 0,
00512 11, 2, 1, 0, 0, 1, 1,
00513 12, 2, 1, 1, 1, 0, 0,
00514 13, 1, 0, 1, 0, 1, 1,
00515 14, 4, 1, 0, 1, 0, 0,
00516 15, 4, 0, 1, 0, 0, 1,
00517 16, 1, 1, 1, 0, 1, 1,
00518 17, 2, 1, 0, 1, 1, 0,
00519 18, 1, 0, 0, 0, 0, 1,
00520 19, 1, 1, 1, 1, 1, 0,
00521 20, 1, 1, 1, 0, 0, 1,
00522 21, 1, 0, 1, 1, 1, 0,
00523 };
00524
00525
00526
00527
00528 const int p3[] = {
00529 100, 5, 25,
00530 1, 2, 1, 2, 1,
00531 2, 3, 3, 5, 5,
00532 0, 7, 1, 0, 0, 1, 0,
00533 1, 11, 1, 1, 0, 0, 0,
00534 2, 1, 0, 1, 1, 1, 1,
00535 3, 3, 1, 0, 1, 0, 0,
00536 4, 15, 0, 1, 0, 0, 0,
00537 5, 2, 1, 0, 1, 1, 0,
00538 6, 8, 0, 1, 0, 1, 0,
00539 7, 5, 0, 0, 1, 0, 0,
00540 8, 3, 0, 0, 0, 1, 0,
00541 9, 4, 0, 1, 1, 1, 0,
00542 10, 5, 1, 0, 0, 0, 0,
00543 11, 2, 1, 1, 1, 0, 1,
00544 12, 6, 0, 1, 1, 0, 0,
00545 13, 2, 0, 0, 1, 0, 1,
00546 14, 2, 0, 1, 0, 0, 1,
00547 15, 4, 1, 1, 1, 1, 0,
00548 16, 3, 1, 0, 0, 0, 1,
00549 17, 5, 1, 1, 0, 1, 0,
00550 18, 2, 1, 1, 1, 0, 0,
00551 19, 4, 1, 1, 0, 0, 1,
00552 20, 1, 1, 0, 0, 1, 1,
00553 21, 1, 1, 1, 0, 1, 1,
00554 22, 1, 0, 1, 0, 1, 1,
00555 23, 1, 0, 1, 1, 0, 1,
00556 24, 2, 0, 0, 0, 0, 1,
00557 };
00558
00559
00560
00561
00562 const int p4[] = {
00563 100, 5, 26,
00564 1, 2, 1, 2, 1,
00565 2, 3, 3, 5, 5,
00566 0, 10, 1, 0, 0, 0, 0,
00567 1, 2, 0, 0, 0, 0, 1,
00568 2, 8, 0, 1, 0, 1, 0,
00569 3, 8, 0, 0, 0, 1, 0,
00570 4, 6, 0, 1, 1, 0, 0,
00571 5, 11, 0, 1, 0, 0, 0,
00572 6, 3, 0, 0, 1, 0, 0,
00573 7, 2, 0, 0, 1, 1, 0,
00574 8, 7, 1, 1, 0, 0, 0,
00575 9, 2, 1, 0, 0, 1, 1,
00576 10, 4, 1, 0, 1, 0, 0,
00577 11, 7, 1, 0, 0, 1, 0,
00578 12, 1, 1, 1, 1, 0, 1,
00579 13, 3, 0, 1, 1, 1, 0,
00580 14, 4, 0, 1, 0, 0, 1,
00581 15, 5, 1, 1, 1, 0, 0,
00582 16, 2, 1, 1, 0, 0, 1,
00583 17, 1, 1, 0, 1, 1, 1,
00584 18, 2, 1, 0, 1, 1, 0,
00585 19, 3, 1, 0, 0, 0, 1,
00586 20, 2, 0, 1, 1, 0, 1,
00587 21, 1, 0, 1, 0, 1, 1,
00588 22, 3, 1, 1, 0, 1, 0,
00589 23, 1, 0, 0, 1, 1, 1,
00590 24, 1, 1, 1, 1, 1, 1,
00591 25, 1, 1, 1, 1, 1, 0,
00592 };
00593
00594
00595
00596
00597 const int p5[] = {
00598 100, 5, 23,
00599 1, 2, 1, 2, 1,
00600 2, 3, 3, 5, 5,
00601 0, 2, 0, 0, 0, 1, 1,
00602 1, 2, 0, 0, 1, 0, 1,
00603 2, 5, 0, 1, 1, 1, 0,
00604 3, 4, 0, 0, 0, 1, 0,
00605 4, 4, 0, 1, 0, 1, 0,
00606 5, 1, 1, 1, 0, 0, 1,
00607 6, 3, 1, 1, 1, 0, 1,
00608 7, 4, 0, 0, 1, 0, 0,
00609 8, 19, 0, 1, 0, 0, 0,
00610 9, 7, 1, 1, 0, 1, 0,
00611 10, 10, 1, 0, 0, 0, 0,
00612 11, 1, 0, 0, 1, 1, 0,
00613 12, 5, 1, 1, 1, 1, 0,
00614 13, 2, 1, 0, 1, 1, 0,
00615 14, 6, 1, 1, 0, 0, 0,
00616 15, 4, 1, 1, 1, 0, 0,
00617 16, 8, 1, 0, 0, 1, 0,
00618 17, 1, 1, 0, 0, 0, 1,
00619 18, 4, 0, 1, 1, 0, 0,
00620 19, 2, 0, 0, 0, 0, 1,
00621 20, 4, 0, 1, 0, 0, 1,
00622 21, 1, 1, 1, 0, 1, 1,
00623 22, 1, 0, 1, 1, 0, 1,
00624 };
00625
00626 const int* problems[] = {
00627 &p0[0],
00628 &p1[0],
00629 &p2[0],
00630 &p3[0],
00631 &p4[0],
00632 &p5[0],
00633 };
00634
00636 const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00637 };
00638
00639
00640