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