car-sequencing.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 // Problems 00047 namespace { 00048 // Problem data 00049 extern const int* problems[]; 00050 // Number of problems 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 // Add options 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 // Find number of required positions 00159 int min = 0; 00160 for (int i = x.size(); i-- && x[i].min() >= val-1; ) { 00161 ++min; 00162 } 00163 // Find number of possible positions 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 // No variables later than max can have value val 00172 while (i--) { 00173 GECODE_ME_CHECK(x[i].le(home, val)); 00174 } 00175 00176 // Constrain y to be in {min..max} 00177 GECODE_ME_CHECK(y.gq(home, min)); 00178 GECODE_ME_CHECK(y.lq(home, max)); 00179 00180 // At least the y.min() last values have value val 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 // Read problem 00263 const int* probit = problems[problem] + 3; 00264 00265 // Sequence requirements for the options. 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 // Number of cars per class 00274 IntArgs ncc(nclasses); 00275 // What classes require an option 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 // Read data 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 // Transfer specification data to int-sets 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 // Count the cars 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 // Count number of end and stallss 00309 count(*this, s, stallval, IRT_EQ, nstall); 00310 count(*this, s, endval, IRT_EQ, nend); 00311 rel(*this, nstall+nend == maxstall); 00312 00313 // Make sure nothing is overloaded 00314 IntSet one(1, 1); 00315 for (int o = noptions; o--; ) { 00316 // sb[i] reflects if car s[i] has option o 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 // End-markers located at end only 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 // Branching 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 // Problem 4/72 (Regin & Puget // 1) 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 // Problem 6/76, (Regin & Puget // 2) 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 // Problem 10/93, (Regin & Puget // 3) 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 // Problem 16/81, 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 // Problem 19/71, (Regin & Puget // 4) 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 // STATISTICS: example-any 00649