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 : Script(opt),
00249 problem(opt.size()),
00250 ncars(problems[problem][0]),
00251 noptions(problems[problem][1]),
00252 nclasses(problems[problem][2]),
00253 maxstall(opt.maxstall()),
00254 stallval(nclasses),
00255 endval(nclasses+1),
00256 nstall(*this, 0, maxstall),
00257 nend(*this, 0, maxstall),
00258 s(*this, ncars+maxstall, 0, nclasses+1)
00259 {
00260
00261 const int* probit = problems[problem] + 3;
00262
00263
00264 IntArgs max(noptions), block(noptions);
00265 for (int i = 0; i < noptions; ++i ) {
00266 max[i] = *probit++;
00267 }
00268 for (int i = 0; i < noptions; ++i ) {
00269 block[i] = *probit++;
00270 }
00271
00272 IntArgs ncc(nclasses);
00273
00274 IntSetArgs classes(noptions);
00275 int** cdata = new int*[noptions];
00276 for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00277 int* n = new int[noptions];
00278 for (int i = noptions; i--; ) n[i] = 0;
00279
00280 for (int c = 0; c < nclasses; ++c) {
00281 probit++;
00282 ncc[c] = *probit++;
00283 for (int o = 0; o < noptions; ++o) {
00284 if (*probit++) {
00285 cdata[o][n[o]++] = c;
00286 }
00287 }
00288 }
00289
00290 for (int o = noptions; o--; ) {
00291 classes[o] = IntSet(cdata[o], n[o]);
00292 delete [] cdata[o];
00293 }
00294 delete [] cdata;
00295 delete [] n;
00296
00297
00298 {
00299 IntSetArgs c(nclasses+2);
00300 for (int i = nclasses; i--; ) {
00301 c[i] = IntSet(ncc[i], ncc[i]);
00302 }
00303 c[stallval] = IntSet(0, maxstall);
00304 c[ endval] = IntSet(0, maxstall);
00305 count(*this, s, c);
00306 }
00307
00308
00309 count(*this, s, stallval, IRT_EQ, nstall);
00310 count(*this, s, endval, IRT_EQ, nend);
00311 rel(*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 rel(*this, (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.branching(CarSequencing::BRANCH_INORDER);
00431 opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
00432 opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00433 opt.propagation(CarSequencing::PROP_CUSTOM);
00434 opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00435 opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
00436 opt.parse(argc,argv);
00437 if (opt.size() >= n_problems) {
00438 std::cerr << "Error: size must be between 0 and "
00439 << n_problems-1 << std::endl;
00440 return 1;
00441 }
00442
00443 Script::run<CarSequencing,BAB,CarOptions>(opt);
00444 return 0;
00445 }
00446
00447
00448 namespace {
00450
00452 const int p0[] = {
00453 10, 5, 6,
00454 1, 2, 1, 2, 1,
00455 2, 3, 3, 5, 5,
00456 0, 1, 1, 0, 1, 1, 0,
00457 1, 1, 0, 0, 0, 1, 0,
00458 2, 2, 0, 1, 0, 0, 1,
00459 3, 2, 0, 1, 0, 1, 0,
00460 4, 2, 1, 0, 1, 0, 0,
00461 5, 2, 1, 1, 0, 0, 0
00462 };
00463
00464
00465
00466
00467 const int p1[] = {
00468 100, 5, 22,
00469 1, 2, 1, 2, 1,
00470 2, 3, 3, 5, 5,
00471 0, 6, 1, 0, 0, 1, 0,
00472 1, 10, 1, 1, 1, 0, 0,
00473 2, 2, 1, 1, 0, 0, 1,
00474 3, 2, 0, 1, 1, 0, 0,
00475 4, 8, 0, 0, 0, 1, 0,
00476 5, 15, 0, 1, 0, 0, 0,
00477 6, 1, 0, 1, 1, 1, 0,
00478 7, 5, 0, 0, 1, 1, 0,
00479 8, 2, 1, 0, 1, 1, 0,
00480 9, 3, 0, 0, 1, 0, 0,
00481 10, 2, 1, 0, 1, 0, 0,
00482 11, 1, 1, 1, 1, 0, 1,
00483 12, 8, 0, 1, 0, 1, 0,
00484 13, 3, 1, 0, 0, 1, 1,
00485 14, 10, 1, 0, 0, 0, 0,
00486 15, 4, 0, 1, 0, 0, 1,
00487 16, 4, 0, 0, 0, 0, 1,
00488 17, 2, 1, 0, 0, 0, 1,
00489 18, 4, 1, 1, 0, 0, 0,
00490 19, 6, 1, 1, 0, 1, 0,
00491 20, 1, 1, 0, 1, 0, 1,
00492 21, 1, 1, 1, 1, 1, 1,
00493 };
00494
00495
00496
00497
00498 const int p2[] = {
00499 100, 5, 22,
00500 1, 2, 1, 2, 1,
00501 2, 3, 3, 5, 5,
00502 0, 13, 1, 0, 0, 0, 0,
00503 1, 8, 0, 0, 0, 1, 0,
00504 2, 7, 0, 1, 0, 0, 0,
00505 3, 1, 1, 0, 0, 1, 0,
00506 4, 12, 0, 0, 1, 0, 0,
00507 5, 5, 0, 1, 0, 1, 0,
00508 6, 5, 0, 0, 1, 1, 0,
00509 7, 6, 0, 1, 1, 0, 0,
00510 8, 3, 1, 0, 0, 0, 1,
00511 9, 12, 1, 1, 0, 0, 0,
00512 10, 8, 1, 1, 0, 1, 0,
00513 11, 2, 1, 0, 0, 1, 1,
00514 12, 2, 1, 1, 1, 0, 0,
00515 13, 1, 0, 1, 0, 1, 1,
00516 14, 4, 1, 0, 1, 0, 0,
00517 15, 4, 0, 1, 0, 0, 1,
00518 16, 1, 1, 1, 0, 1, 1,
00519 17, 2, 1, 0, 1, 1, 0,
00520 18, 1, 0, 0, 0, 0, 1,
00521 19, 1, 1, 1, 1, 1, 0,
00522 20, 1, 1, 1, 0, 0, 1,
00523 21, 1, 0, 1, 1, 1, 0,
00524 };
00525
00526
00527
00528
00529 const int p3[] = {
00530 100, 5, 25,
00531 1, 2, 1, 2, 1,
00532 2, 3, 3, 5, 5,
00533 0, 7, 1, 0, 0, 1, 0,
00534 1, 11, 1, 1, 0, 0, 0,
00535 2, 1, 0, 1, 1, 1, 1,
00536 3, 3, 1, 0, 1, 0, 0,
00537 4, 15, 0, 1, 0, 0, 0,
00538 5, 2, 1, 0, 1, 1, 0,
00539 6, 8, 0, 1, 0, 1, 0,
00540 7, 5, 0, 0, 1, 0, 0,
00541 8, 3, 0, 0, 0, 1, 0,
00542 9, 4, 0, 1, 1, 1, 0,
00543 10, 5, 1, 0, 0, 0, 0,
00544 11, 2, 1, 1, 1, 0, 1,
00545 12, 6, 0, 1, 1, 0, 0,
00546 13, 2, 0, 0, 1, 0, 1,
00547 14, 2, 0, 1, 0, 0, 1,
00548 15, 4, 1, 1, 1, 1, 0,
00549 16, 3, 1, 0, 0, 0, 1,
00550 17, 5, 1, 1, 0, 1, 0,
00551 18, 2, 1, 1, 1, 0, 0,
00552 19, 4, 1, 1, 0, 0, 1,
00553 20, 1, 1, 0, 0, 1, 1,
00554 21, 1, 1, 1, 0, 1, 1,
00555 22, 1, 0, 1, 0, 1, 1,
00556 23, 1, 0, 1, 1, 0, 1,
00557 24, 2, 0, 0, 0, 0, 1,
00558 };
00559
00560
00561
00562
00563 const int p4[] = {
00564 100, 5, 26,
00565 1, 2, 1, 2, 1,
00566 2, 3, 3, 5, 5,
00567 0, 10, 1, 0, 0, 0, 0,
00568 1, 2, 0, 0, 0, 0, 1,
00569 2, 8, 0, 1, 0, 1, 0,
00570 3, 8, 0, 0, 0, 1, 0,
00571 4, 6, 0, 1, 1, 0, 0,
00572 5, 11, 0, 1, 0, 0, 0,
00573 6, 3, 0, 0, 1, 0, 0,
00574 7, 2, 0, 0, 1, 1, 0,
00575 8, 7, 1, 1, 0, 0, 0,
00576 9, 2, 1, 0, 0, 1, 1,
00577 10, 4, 1, 0, 1, 0, 0,
00578 11, 7, 1, 0, 0, 1, 0,
00579 12, 1, 1, 1, 1, 0, 1,
00580 13, 3, 0, 1, 1, 1, 0,
00581 14, 4, 0, 1, 0, 0, 1,
00582 15, 5, 1, 1, 1, 0, 0,
00583 16, 2, 1, 1, 0, 0, 1,
00584 17, 1, 1, 0, 1, 1, 1,
00585 18, 2, 1, 0, 1, 1, 0,
00586 19, 3, 1, 0, 0, 0, 1,
00587 20, 2, 0, 1, 1, 0, 1,
00588 21, 1, 0, 1, 0, 1, 1,
00589 22, 3, 1, 1, 0, 1, 0,
00590 23, 1, 0, 0, 1, 1, 1,
00591 24, 1, 1, 1, 1, 1, 1,
00592 25, 1, 1, 1, 1, 1, 0,
00593 };
00594
00595
00596
00597
00598 const int p5[] = {
00599 100, 5, 23,
00600 1, 2, 1, 2, 1,
00601 2, 3, 3, 5, 5,
00602 0, 2, 0, 0, 0, 1, 1,
00603 1, 2, 0, 0, 1, 0, 1,
00604 2, 5, 0, 1, 1, 1, 0,
00605 3, 4, 0, 0, 0, 1, 0,
00606 4, 4, 0, 1, 0, 1, 0,
00607 5, 1, 1, 1, 0, 0, 1,
00608 6, 3, 1, 1, 1, 0, 1,
00609 7, 4, 0, 0, 1, 0, 0,
00610 8, 19, 0, 1, 0, 0, 0,
00611 9, 7, 1, 1, 0, 1, 0,
00612 10, 10, 1, 0, 0, 0, 0,
00613 11, 1, 0, 0, 1, 1, 0,
00614 12, 5, 1, 1, 1, 1, 0,
00615 13, 2, 1, 0, 1, 1, 0,
00616 14, 6, 1, 1, 0, 0, 0,
00617 15, 4, 1, 1, 1, 0, 0,
00618 16, 8, 1, 0, 0, 1, 0,
00619 17, 1, 1, 0, 0, 0, 1,
00620 18, 4, 0, 1, 1, 0, 0,
00621 19, 2, 0, 0, 0, 0, 1,
00622 20, 4, 0, 1, 0, 0, 1,
00623 21, 1, 1, 1, 0, 1, 1,
00624 22, 1, 0, 1, 1, 0, 1,
00625 };
00626
00627 const int* problems[] = {
00628 &p0[0],
00629 &p1[0],
00630 &p2[0],
00631 &p3[0],
00632 &p4[0],
00633 &p5[0],
00634 };
00635
00637 const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00638 };
00639
00640
00641