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 int i = x.size();
00166 while (i--) {
00167 if (x[i].max() != val) break;
00168 ++max;
00169 if (max >= y.max()) break;
00170 }
00171
00172 while (i--) {
00173 GECODE_ME_CHECK(x[i].le(home, val));
00174 }
00175
00176
00177 GECODE_ME_CHECK(y.gq(home, min));
00178 GECODE_ME_CHECK(y.lq(home, max));
00179
00180
00181 for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
00182 GECODE_ME_CHECK(x[pos].eq(home, val));
00183 }
00184
00185 return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00186 }
00187
00190 void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
00191 ViewArray<Int::IntView> vx(home, x);
00192 Int::IntView vy(y);
00193 GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
00194 }
00195
00196 }
00197
00198
00210 class CarSequencing : public Script {
00211 public:
00213 enum {
00214 SEARCH_BAB,
00215 SEARCH_RESTART
00216 };
00218 enum {
00219 BRANCH_INORDER,
00220 BRANCH_MIDDLE
00221 };
00223 enum {
00224 PROP_REGULAR,
00225 PROP_CUSTOM
00226 };
00227 protected:
00229 const int problem;
00231 const int ncars;
00233 const int noptions;
00235 const int nclasses;
00237 const int maxstall;
00239 const int stallval;
00241 const int endval;
00243 IntVar nstall;
00245 IntVar nend;
00247 IntVarArray s;
00248 public:
00250 CarSequencing(const CarOptions& opt)
00251 : problem(opt.size()),
00252 ncars(problems[problem][0]),
00253 noptions(problems[problem][1]),
00254 nclasses(problems[problem][2]),
00255 maxstall(opt.maxstall()),
00256 stallval(nclasses),
00257 endval(nclasses+1),
00258 nstall(*this, 0, maxstall),
00259 nend(*this, 0, maxstall),
00260 s(*this, ncars+maxstall, 0, nclasses+1)
00261 {
00262
00263 const int* probit = problems[problem] + 3;
00264
00265
00266 IntArgs max(noptions), block(noptions);
00267 for (int i = 0; i < noptions; ++i ) {
00268 max[i] = *probit++;
00269 }
00270 for (int i = 0; i < noptions; ++i ) {
00271 block[i] = *probit++;
00272 }
00273
00274 IntArgs ncc(nclasses);
00275
00276 IntSetArgs classes(noptions);
00277 int** cdata = new int*[noptions];
00278 for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00279 int* n = new int[noptions];
00280 for (int i = noptions; i--; ) n[i] = 0;
00281
00282 for (int c = 0; c < nclasses; ++c) {
00283 *probit++;
00284 ncc[c] = *probit++;
00285 for (int o = 0; o < noptions; ++o) {
00286 if (*probit++) {
00287 cdata[o][n[o]++] = c;
00288 }
00289 }
00290 }
00291
00292 for (int o = noptions; o--; ) {
00293 classes[o] = IntSet(cdata[o], n[o]);
00294 delete [] cdata[o];
00295 }
00296 delete [] cdata;
00297 delete [] n;
00298
00299
00300 IntSetArgs c(nclasses+2);
00301 for (int i = nclasses; i--; ) {
00302 c[i] = IntSet(ncc[i], ncc[i]);
00303 }
00304 c[stallval] = IntSet(0, maxstall);
00305 c[ endval] = IntSet(0, maxstall);
00306 count(*this, s, c);
00307
00308
00309 count(*this, s, stallval, IRT_EQ, nstall);
00310 count(*this, s, endval, IRT_EQ, nend);
00311 post(*this, nstall+nend == maxstall);
00312
00313
00314 IntSet one(1, 1);
00315 for (int o = noptions; o--; ) {
00316
00317 BoolVarArgs sb(s.size());
00318 for (int i = s.size(); i--; ) {
00319 BoolVar b(*this, 0, 1);
00320 dom(*this, s[i], classes[o], b);
00321 sb[i] = b;
00322 }
00323 sequence(*this, sb, one, block[o], 0, max[o]);
00324 }
00325
00326
00327 switch (opt.propagation()) {
00328 case PROP_REGULAR: {
00329 IntArgs notend(nclasses), notstallend(nclasses+1);
00330 for (int i = nclasses; i--; ) {
00331 notend[i] = i;
00332 notstallend[i] = i;
00333 }
00334 notstallend[nclasses] = stallval;
00335 REG r = *REG(notend) + REG(notstallend) + *REG(endval);
00336 extensional(*this, s, r);
00337 for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
00338 post(*this, imp(~(nend > i), ~(s[pos]==endval)));
00339 }
00340 } break;
00341 case PROP_CUSTOM: {
00342 pushtoend(*this, s, nend, endval);
00343 } break;
00344 }
00345
00346
00347
00348 switch (opt.branching()) {
00349 case BRANCH_INORDER:
00350 branch(*this, s, INT_VAR_NONE, INT_VAL_MIN);
00351 break;
00352 case BRANCH_MIDDLE: {
00353 IntVarArgs m(s.size());
00354 int mid = s.size() / 2;
00355 int pos = 0;
00356 m[pos++] = s[mid];
00357 for (int i = 1; i <= m.size()/2; ++i) {
00358 if (mid-i >= 0)
00359 m[pos++] = s[mid-i];
00360 if (mid+i < s.size())
00361 m[pos++] = s[mid+i];
00362 }
00363 assert(pos == m.size());
00364 branch(*this, m, INT_VAR_NONE, INT_VAL_MIN);
00365 break;
00366 }
00367 }
00368 }
00369
00371 virtual void constrain(const Space& _best) {
00372 const CarSequencing& best = static_cast<const CarSequencing&>(_best);
00373 rel(*this, nstall, IRT_LE, best.nstall.val());
00374 }
00375
00377 virtual void
00378 print(std::ostream& os) const {
00379 int width = nclasses > 9 ? 2 : 1;
00380 const char* space = nclasses > 9 ? " " : "";
00381 os << "Stall slots=" << nstall
00382 << ", End slots=" << nend << std::endl;
00383 int i = 0;
00384 for (; i < s.size(); ++i) {
00385 if (s[i].assigned()) {
00386 int v = s[i].val();
00387 if (v == endval) break;
00388 if (v == stallval) os << space << "_ ";
00389 else os << std::setw(width) << v << " ";
00390 } else {
00391 os << space << "? ";
00392 }
00393 if ((i+1)%20 == 0) os << std::endl;
00394 }
00395 if (i%20)
00396 os << std::endl;
00397 os << std::endl;
00398 }
00399
00401 CarSequencing(bool share, CarSequencing& cs)
00402 : Script(share,cs),
00403 problem(cs.problem),
00404 ncars(cs.ncars),
00405 noptions(cs.noptions),
00406 nclasses(cs.nclasses),
00407 maxstall(cs.maxstall),
00408 stallval(cs.stallval),
00409 endval(cs.endval)
00410 {
00411 nstall.update(*this, share, cs.nstall);
00412 nend.update(*this, share, cs.nend);
00413 s.update(*this, share, cs.s);
00414 }
00416 virtual Space*
00417 copy(bool share) {
00418 return new CarSequencing(share,*this);
00419 }
00420 };
00421
00425 int
00426 main(int argc, char* argv[]) {
00427 CarOptions opt("CarSequencing");
00428 opt.solutions(0);
00429 opt.size(0);
00430 opt.search(CarSequencing::SEARCH_BAB);
00431 opt.search(CarSequencing::SEARCH_BAB, "bab");
00432 opt.search(CarSequencing::SEARCH_RESTART, "restart");
00433 opt.branching(CarSequencing::BRANCH_INORDER);
00434 opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
00435 opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00436 opt.propagation(CarSequencing::PROP_CUSTOM);
00437 opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00438 opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
00439 opt.parse(argc,argv);
00440 if (opt.size() >= n_problems) {
00441 std::cerr << "Error: size must be between 0 and "
00442 << n_problems-1 << std::endl;
00443 return 1;
00444 }
00445
00446 switch (opt.search()) {
00447 case CarSequencing::SEARCH_BAB:
00448 Script::run<CarSequencing,BAB,CarOptions>(opt); break;
00449 case CarSequencing::SEARCH_RESTART:
00450 Script::run<CarSequencing,Restart,CarOptions>(opt); break;
00451 }
00452 return 0;
00453 }
00454
00455
00456 namespace {
00458
00460 const int p0[] = {
00461 10, 5, 6,
00462 1, 2, 1, 2, 1,
00463 2, 3, 3, 5, 5,
00464 0, 1, 1, 0, 1, 1, 0,
00465 1, 1, 0, 0, 0, 1, 0,
00466 2, 2, 0, 1, 0, 0, 1,
00467 3, 2, 0, 1, 0, 1, 0,
00468 4, 2, 1, 0, 1, 0, 0,
00469 5, 2, 1, 1, 0, 0, 0
00470 };
00471
00472
00473
00474
00475 const int p1[] = {
00476 100, 5, 22,
00477 1, 2, 1, 2, 1,
00478 2, 3, 3, 5, 5,
00479 0, 6, 1, 0, 0, 1, 0,
00480 1, 10, 1, 1, 1, 0, 0,
00481 2, 2, 1, 1, 0, 0, 1,
00482 3, 2, 0, 1, 1, 0, 0,
00483 4, 8, 0, 0, 0, 1, 0,
00484 5, 15, 0, 1, 0, 0, 0,
00485 6, 1, 0, 1, 1, 1, 0,
00486 7, 5, 0, 0, 1, 1, 0,
00487 8, 2, 1, 0, 1, 1, 0,
00488 9, 3, 0, 0, 1, 0, 0,
00489 10, 2, 1, 0, 1, 0, 0,
00490 11, 1, 1, 1, 1, 0, 1,
00491 12, 8, 0, 1, 0, 1, 0,
00492 13, 3, 1, 0, 0, 1, 1,
00493 14, 10, 1, 0, 0, 0, 0,
00494 15, 4, 0, 1, 0, 0, 1,
00495 16, 4, 0, 0, 0, 0, 1,
00496 17, 2, 1, 0, 0, 0, 1,
00497 18, 4, 1, 1, 0, 0, 0,
00498 19, 6, 1, 1, 0, 1, 0,
00499 20, 1, 1, 0, 1, 0, 1,
00500 21, 1, 1, 1, 1, 1, 1,
00501 };
00502
00503
00504
00505
00506 const int p2[] = {
00507 100, 5, 22,
00508 1, 2, 1, 2, 1,
00509 2, 3, 3, 5, 5,
00510 0, 13, 1, 0, 0, 0, 0,
00511 1, 8, 0, 0, 0, 1, 0,
00512 2, 7, 0, 1, 0, 0, 0,
00513 3, 1, 1, 0, 0, 1, 0,
00514 4, 12, 0, 0, 1, 0, 0,
00515 5, 5, 0, 1, 0, 1, 0,
00516 6, 5, 0, 0, 1, 1, 0,
00517 7, 6, 0, 1, 1, 0, 0,
00518 8, 3, 1, 0, 0, 0, 1,
00519 9, 12, 1, 1, 0, 0, 0,
00520 10, 8, 1, 1, 0, 1, 0,
00521 11, 2, 1, 0, 0, 1, 1,
00522 12, 2, 1, 1, 1, 0, 0,
00523 13, 1, 0, 1, 0, 1, 1,
00524 14, 4, 1, 0, 1, 0, 0,
00525 15, 4, 0, 1, 0, 0, 1,
00526 16, 1, 1, 1, 0, 1, 1,
00527 17, 2, 1, 0, 1, 1, 0,
00528 18, 1, 0, 0, 0, 0, 1,
00529 19, 1, 1, 1, 1, 1, 0,
00530 20, 1, 1, 1, 0, 0, 1,
00531 21, 1, 0, 1, 1, 1, 0,
00532 };
00533
00534
00535
00536
00537 const int p3[] = {
00538 100, 5, 25,
00539 1, 2, 1, 2, 1,
00540 2, 3, 3, 5, 5,
00541 0, 7, 1, 0, 0, 1, 0,
00542 1, 11, 1, 1, 0, 0, 0,
00543 2, 1, 0, 1, 1, 1, 1,
00544 3, 3, 1, 0, 1, 0, 0,
00545 4, 15, 0, 1, 0, 0, 0,
00546 5, 2, 1, 0, 1, 1, 0,
00547 6, 8, 0, 1, 0, 1, 0,
00548 7, 5, 0, 0, 1, 0, 0,
00549 8, 3, 0, 0, 0, 1, 0,
00550 9, 4, 0, 1, 1, 1, 0,
00551 10, 5, 1, 0, 0, 0, 0,
00552 11, 2, 1, 1, 1, 0, 1,
00553 12, 6, 0, 1, 1, 0, 0,
00554 13, 2, 0, 0, 1, 0, 1,
00555 14, 2, 0, 1, 0, 0, 1,
00556 15, 4, 1, 1, 1, 1, 0,
00557 16, 3, 1, 0, 0, 0, 1,
00558 17, 5, 1, 1, 0, 1, 0,
00559 18, 2, 1, 1, 1, 0, 0,
00560 19, 4, 1, 1, 0, 0, 1,
00561 20, 1, 1, 0, 0, 1, 1,
00562 21, 1, 1, 1, 0, 1, 1,
00563 22, 1, 0, 1, 0, 1, 1,
00564 23, 1, 0, 1, 1, 0, 1,
00565 24, 2, 0, 0, 0, 0, 1,
00566 };
00567
00568
00569
00570
00571 const int p4[] = {
00572 100, 5, 26,
00573 1, 2, 1, 2, 1,
00574 2, 3, 3, 5, 5,
00575 0, 10, 1, 0, 0, 0, 0,
00576 1, 2, 0, 0, 0, 0, 1,
00577 2, 8, 0, 1, 0, 1, 0,
00578 3, 8, 0, 0, 0, 1, 0,
00579 4, 6, 0, 1, 1, 0, 0,
00580 5, 11, 0, 1, 0, 0, 0,
00581 6, 3, 0, 0, 1, 0, 0,
00582 7, 2, 0, 0, 1, 1, 0,
00583 8, 7, 1, 1, 0, 0, 0,
00584 9, 2, 1, 0, 0, 1, 1,
00585 10, 4, 1, 0, 1, 0, 0,
00586 11, 7, 1, 0, 0, 1, 0,
00587 12, 1, 1, 1, 1, 0, 1,
00588 13, 3, 0, 1, 1, 1, 0,
00589 14, 4, 0, 1, 0, 0, 1,
00590 15, 5, 1, 1, 1, 0, 0,
00591 16, 2, 1, 1, 0, 0, 1,
00592 17, 1, 1, 0, 1, 1, 1,
00593 18, 2, 1, 0, 1, 1, 0,
00594 19, 3, 1, 0, 0, 0, 1,
00595 20, 2, 0, 1, 1, 0, 1,
00596 21, 1, 0, 1, 0, 1, 1,
00597 22, 3, 1, 1, 0, 1, 0,
00598 23, 1, 0, 0, 1, 1, 1,
00599 24, 1, 1, 1, 1, 1, 1,
00600 25, 1, 1, 1, 1, 1, 0,
00601 };
00602
00603
00604
00605
00606 const int p5[] = {
00607 100, 5, 23,
00608 1, 2, 1, 2, 1,
00609 2, 3, 3, 5, 5,
00610 0, 2, 0, 0, 0, 1, 1,
00611 1, 2, 0, 0, 1, 0, 1,
00612 2, 5, 0, 1, 1, 1, 0,
00613 3, 4, 0, 0, 0, 1, 0,
00614 4, 4, 0, 1, 0, 1, 0,
00615 5, 1, 1, 1, 0, 0, 1,
00616 6, 3, 1, 1, 1, 0, 1,
00617 7, 4, 0, 0, 1, 0, 0,
00618 8, 19, 0, 1, 0, 0, 0,
00619 9, 7, 1, 1, 0, 1, 0,
00620 10, 10, 1, 0, 0, 0, 0,
00621 11, 1, 0, 0, 1, 1, 0,
00622 12, 5, 1, 1, 1, 1, 0,
00623 13, 2, 1, 0, 1, 1, 0,
00624 14, 6, 1, 1, 0, 0, 0,
00625 15, 4, 1, 1, 1, 0, 0,
00626 16, 8, 1, 0, 0, 1, 0,
00627 17, 1, 1, 0, 0, 0, 1,
00628 18, 4, 0, 1, 1, 0, 0,
00629 19, 2, 0, 0, 0, 0, 1,
00630 20, 4, 0, 1, 0, 0, 1,
00631 21, 1, 1, 1, 0, 1, 1,
00632 22, 1, 0, 1, 1, 0, 1,
00633 };
00634
00635 const int* problems[] = {
00636 &p0[0],
00637 &p1[0],
00638 &p2[0],
00639 &p3[0],
00640 &p4[0],
00641 &p5[0],
00642 };
00643
00645 const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00646 };
00647
00648
00649