steel-mill.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, 2008 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 <fstream> 00043 00044 using namespace Gecode; 00045 00052 typedef int (*order_t)[2]; 00053 extern const int order_weight; 00054 extern const int order_color; 00055 00056 00062 extern int csplib_capacities[]; 00063 extern unsigned int csplib_ncapacities; 00064 extern unsigned int csplib_maxcapacity; 00065 extern int csplib_loss[]; 00066 extern int csplib_orders[][2]; 00067 extern unsigned int csplib_ncolors; 00068 extern unsigned int csplib_norders; 00069 00070 00071 00077 class SteelMillOptions : public Options { 00078 private: 00079 unsigned int _size; 00080 int* _capacities; 00081 int _ncapacities; 00082 int _maxcapacity; 00083 int* _loss; 00084 order_t _orders; 00085 int _ncolors; 00086 unsigned int _norders; 00087 public: 00089 SteelMillOptions(const char* n) 00090 : Options(n), _size(csplib_norders), 00091 _capacities(csplib_capacities), _ncapacities(csplib_ncapacities), 00092 _maxcapacity(csplib_maxcapacity), 00093 _loss(csplib_loss), _orders(&(csplib_orders[0])), _ncolors(csplib_ncolors), 00094 _norders(csplib_norders) {} 00096 virtual void help(void); 00098 bool parse(int& argc, char* argv[]); 00099 00101 unsigned int size(void) const { return _size; } 00103 int* capacities(void) const { return _capacities; } 00105 int ncapacities(void) const { return _ncapacities; } 00107 int maxcapacity(void) const { return _maxcapacity; } 00109 int* loss(void) const { return _loss; } 00111 order_t orders(void) const { return _orders; } 00113 int ncolors(void) const { return _ncolors; } 00115 int norders(void) const { return _norders; } 00116 }; 00117 00118 00147 class SteelMill : public MinimizeScript { 00148 protected: 00152 int* capacities; 00153 int ncapacities; 00154 int maxcapacity; 00155 int* loss; 00156 int ncolors; 00157 order_t orders; 00158 unsigned int norders; 00159 unsigned int nslabs; 00160 00161 00165 IntVarArray slab, 00166 slabload, 00167 slabcost; 00168 IntVar total_cost; 00169 00170 00171 public: 00173 enum { 00174 SYMMETRY_NONE, 00175 SYMMETRY_BRANCHING 00176 }; 00177 00179 SteelMill(const SteelMillOptions& opt) 00180 : // Initialize instance data 00181 capacities(opt.capacities()), ncapacities(opt.ncapacities()), 00182 maxcapacity(opt.maxcapacity()), loss(opt.loss()), 00183 ncolors(opt.ncolors()), orders(opt.orders()), 00184 norders(opt.size()), nslabs(opt.size()), 00185 // Initialize problem variables 00186 slab(*this, norders, 0,nslabs-1), 00187 slabload(*this, nslabs, 0,45), 00188 slabcost(*this, nslabs, 0, Int::Limits::max), 00189 total_cost(*this, 0, Int::Limits::max) 00190 { 00191 // Boolean variables for slab[o]==s 00192 BoolVarArgs boolslab(norders*nslabs); 00193 for (unsigned int i = 0; i < norders; ++i) { 00194 BoolVarArgs tmp(nslabs); 00195 for (int j = nslabs; j--; ) { 00196 boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1); 00197 } 00198 channel(*this, tmp, slab[i]); 00199 } 00200 00201 // Packing constraints 00202 for (unsigned int s = 0; s < nslabs; ++s) { 00203 IntArgs c(norders); 00204 BoolVarArgs x(norders); 00205 for (int i = norders; i--; ) { 00206 c[i] = orders[i][order_weight]; 00207 x[i] = boolslab[s + i*nslabs]; 00208 } 00209 linear(*this, c, x, IRT_EQ, slabload[s]); 00210 } 00211 // Redundant packing constraint 00212 int totalweight = 0; 00213 for (unsigned int i = norders; i-- ; ) 00214 totalweight += orders[i][order_weight] ; 00215 linear(*this, slabload, IRT_EQ, totalweight); 00216 00217 00218 // Color constraints 00219 IntArgs nofcolor(ncolors); 00220 for (int c = ncolors; c--; ) { 00221 nofcolor[c] = 0; 00222 for (int o = norders; o--; ) { 00223 if (orders[o][order_color] == c) nofcolor[c] += 1; 00224 } 00225 } 00226 BoolVar f(*this, 0, 0); 00227 for (unsigned int s = 0; s < nslabs; ++s) { 00228 BoolVarArgs hascolor(ncolors); 00229 for (int c = ncolors; c--; ) { 00230 if (nofcolor[c]) { 00231 BoolVarArgs hasc(nofcolor[c]); 00232 int pos = 0; 00233 for (int o = norders; o--; ) { 00234 if (orders[o][order_color] == c) 00235 hasc[pos++] = boolslab[s + o*nslabs]; 00236 } 00237 assert(pos == nofcolor[c]); 00238 hascolor[c] = BoolVar(*this, 0, 1); 00239 rel(*this, BOT_OR, hasc, hascolor[c]); 00240 } else { 00241 hascolor[c] = f; 00242 } 00243 } 00244 linear(*this, hascolor, IRT_LQ, 2); 00245 } 00246 00247 // Compute slabcost 00248 IntArgs l(maxcapacity, loss); 00249 for (int s = nslabs; s--; ) { 00250 element(*this, l, slabload[s], slabcost[s]); 00251 } 00252 linear(*this, slabcost, IRT_EQ, total_cost); 00253 00254 // Add branching 00255 if (opt.symmetry() == SYMMETRY_BRANCHING) { 00256 // Symmetry breaking branching 00257 SteelMillBranch::post(*this); 00258 } else { // opt.symmetry() == SYMMETRY_NONE 00259 branch(*this, slab, INT_VAR_MAX_MIN, INT_VAL_MIN); 00260 } 00261 } 00262 00264 virtual void 00265 print(std::ostream& os) const { 00266 os << "What slab=" << slab << std::endl; 00267 os << "Slab load=" << slabload << std::endl; 00268 os << "Slab cost=" << slabcost << std::endl; 00269 os << "Total cost=" << total_cost << std::endl; 00270 int nslabsused = 0; 00271 int nslabscost = 0; 00272 bool unassigned = false; 00273 for (int i = nslabs; i--; ) { 00274 if (!slabload[i].assigned() || !slabcost[i].assigned()) { 00275 unassigned = true; 00276 break; 00277 } 00278 if (slabload[i].min()>0) ++nslabsused; 00279 if (slabcost[i].min()>0) ++nslabscost; 00280 } 00281 if (!unassigned) 00282 os << "Number of slabs used=" << nslabsused 00283 << ", slabs with cost=" << nslabscost 00284 << std::endl; 00285 os << std::endl; 00286 } 00287 00289 SteelMill(bool share, SteelMill& s) 00290 : MinimizeScript(share,s), 00291 capacities(s.capacities), ncapacities(s.ncapacities), 00292 maxcapacity(s.maxcapacity), loss(s.loss), 00293 ncolors(s.ncolors), orders(s.orders), 00294 norders(s.norders), nslabs(s.nslabs) { 00295 slab.update(*this, share, s.slab); 00296 slabload.update(*this, share, s.slabload); 00297 slabcost.update(*this, share, s.slabcost); 00298 total_cost.update(*this, share, s.total_cost); 00299 } 00301 virtual Space* 00302 copy(bool share) { 00303 return new SteelMill(share,*this); 00304 } 00306 virtual IntVar cost(void) const { 00307 return total_cost; 00308 } 00309 00310 00319 class SteelMillBranch : Brancher { 00320 protected: 00322 mutable int start; 00324 class Choice : public Gecode::Choice { 00325 public: 00327 int pos; 00329 int val; 00333 Choice(const Brancher& b, unsigned int a, int pos0, int val0) 00334 : Gecode::Choice(b,a), pos(pos0), val(val0) {} 00336 virtual size_t size(void) const { 00337 return sizeof(Choice); 00338 } 00339 }; 00340 00342 SteelMillBranch(Home home) 00343 : Brancher(home), start(0) {} 00345 SteelMillBranch(Space& home, bool share, SteelMillBranch& b) 00346 : Brancher(home, share, b), start(b.start) { 00347 } 00348 00349 public: 00351 virtual bool status(const Space& home) const { 00352 const SteelMill& sm = static_cast<const SteelMill&>(home); 00353 for (unsigned int i = start; i < sm.norders; ++i) 00354 if (!sm.slab[i].assigned()) { 00355 start = i; 00356 return true; 00357 } 00358 // No non-assigned orders left 00359 return false; 00360 } 00362 virtual Gecode::Choice* choice(Space& home) { 00363 SteelMill& sm = static_cast<SteelMill&>(home); 00364 assert(!sm.slab[start].assigned()); 00365 // Find order with a) minimum size, b) largest weight 00366 unsigned int size = sm.norders; 00367 int weight = 0; 00368 unsigned int pos = start; 00369 for (unsigned int i = start; i<sm.norders; ++i) { 00370 if (!sm.slab[i].assigned()) { 00371 if (sm.slab[i].size() == size && 00372 sm.orders[i][order_weight] > weight) { 00373 weight = sm.orders[i][order_weight]; 00374 pos = i; 00375 } else if (sm.slab[i].size() < size) { 00376 size = sm.slab[i].size(); 00377 weight = sm.orders[i][order_weight]; 00378 pos = i; 00379 } 00380 } 00381 } 00382 unsigned int val = sm.slab[pos].min(); 00383 // Find first still empty slab (all such slabs are symmetric) 00384 unsigned int firstzero = 0; 00385 while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0) 00386 ++firstzero; 00387 assert(pos < sm.nslabs && 00388 val < sm.norders); 00389 return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val); 00390 } 00392 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c, 00393 unsigned int a) { 00394 SteelMill& sm = static_cast<SteelMill&>(home); 00395 const Choice& c = static_cast<const Choice&>(_c); 00396 if (a) 00397 return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val)) 00398 ? ES_FAILED : ES_OK; 00399 else 00400 return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val)) 00401 ? ES_FAILED : ES_OK; 00402 } 00404 virtual Actor* copy(Space& home, bool share) { 00405 return new (home) SteelMillBranch(home, share, *this); 00406 } 00408 static void post(Home home) { 00409 (void) new (home) SteelMillBranch(home); 00410 } 00412 virtual size_t dispose(Space&) { 00413 return sizeof(*this); 00414 } 00415 }; 00416 }; 00417 00421 int 00422 main(int argc, char* argv[]) { 00423 SteelMillOptions opt("Steel Mill Slab design"); 00424 opt.symmetry(SteelMill::SYMMETRY_BRANCHING); 00425 opt.symmetry(SteelMill::SYMMETRY_NONE,"none"); 00426 opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching"); 00427 opt.solutions(0); 00428 if (!opt.parse(argc,argv)) 00429 return 1; 00430 Script::run<SteelMill,BAB,SteelMillOptions>(opt); 00431 return 0; 00432 } 00433 00434 00435 void 00436 SteelMillOptions::help(void) { 00437 Options::help(); 00438 std::cerr << "\t(string), optional" << std::endl 00439 << "\t\tBenchmark to load." << std::endl 00440 << "\t\tIf none is given, the standard CSPLib instance is used." 00441 << std::endl; 00442 std::cerr << "\t(unsigned int), optional" << std::endl 00443 << "\t\tNumber of orders to use, in the interval [0..norders]." 00444 << std::endl 00445 << "\t\tIf none is given, all orders are used." << std::endl; 00446 } 00447 00448 bool 00449 SteelMillOptions::parse(int& argc, char* argv[]) { 00450 Options::parse(argc,argv); 00451 // Check number of arguments 00452 if (argc >= 4) { 00453 std::cerr << "Too many arguments given, max two allowed (given={"; 00454 for (int i = 1; i < argc; ++i) { 00455 std::cerr << "\"" << argv[i] << "\""; 00456 if (i < argc-1) std::cerr << ","; 00457 } 00458 std::cerr << "})." << std::endl; 00459 return false; 00460 } 00461 // Parse options 00462 while (argc >= 2) { 00463 bool issize = true; 00464 for (int i = strlen(argv[argc-1]); i-- && issize; ) 00465 issize &= (isdigit(argv[argc-1][i]) != 0); 00466 if (issize) { 00467 _size = atoi(argv[argc-1]); 00468 } else { 00469 std::ifstream instance(argv[argc-1]); 00470 if (instance.fail()) { 00471 std::cerr << "Argument \"" << argv[argc-1] 00472 << "\" is neither an integer nor a readable file" 00473 << std::endl; 00474 return false; 00475 } 00476 // Read file instance 00477 instance >> _ncapacities; 00478 _capacities = new int[_ncapacities]; 00479 _maxcapacity = -1; 00480 for (int i = 0; i < _ncapacities; ++i) { 00481 instance >> _capacities[i]; 00482 _maxcapacity = std::max(_maxcapacity, _capacities[i]); 00483 } 00484 instance >> _ncolors >> _norders; 00485 _orders = new int[_norders][2]; 00486 for (unsigned int i = 0; i < _norders; ++i) { 00487 instance >> _orders[i][order_weight] >> _orders[i][order_color]; 00488 } 00489 } 00490 00491 --argc; 00492 } 00493 // Compute loss 00494 { 00495 _loss = new int[_maxcapacity+1]; 00496 _loss[0] = 0; 00497 int currcap = 0; 00498 for (int c = 1; c < _maxcapacity; ++c) { 00499 if (c > _capacities[currcap]) ++currcap; 00500 _loss[c] = _capacities[currcap] - c; 00501 } 00502 } 00503 // Set size, if none given 00504 if (_size == 0) { 00505 _size = _norders; 00506 } 00507 // Check size reasonability 00508 if (_size == 0 || _size > _norders) { 00509 std::cerr << "Size must be between 1 and " << _norders << std::endl; 00510 return false; 00511 } 00512 return true; 00513 } 00514 00515 // Positions in order array 00516 const int order_weight = 0; 00517 const int order_color = 1; 00518 00519 // CSPLib instance 00520 int csplib_capacities[] = 00521 {12, 14, 17, 18, 19, 00522 20, 23, 24, 25, 26, 00523 27, 28, 29, 30, 32, 00524 35, 39, 42, 43, 44}; 00525 unsigned int csplib_ncapacities = 20; 00526 unsigned int csplib_maxcapacity = 44; 00527 int csplib_loss[45]; 00528 unsigned int csplib_ncolors = 89; 00529 unsigned int csplib_norders = 111; 00530 int csplib_orders[][2] = { 00531 {4, 1}, 00532 {22, 2}, 00533 {9, 3}, 00534 {5, 4}, 00535 {8, 5}, 00536 {3, 6}, 00537 {3, 4}, 00538 {4, 7}, 00539 {7, 4}, 00540 {7, 8}, 00541 {3, 6}, 00542 {2, 6}, 00543 {2, 4}, 00544 {8, 9}, 00545 {5, 10}, 00546 {7, 11}, 00547 {4, 7}, 00548 {7, 11}, 00549 {5, 10}, 00550 {7, 11}, 00551 {8, 9}, 00552 {3, 1}, 00553 {25, 12}, 00554 {14, 13}, 00555 {3, 6}, 00556 {22, 14}, 00557 {19, 15}, 00558 {19, 15}, 00559 {22, 16}, 00560 {22, 17}, 00561 {22, 18}, 00562 {20, 19}, 00563 {22, 20}, 00564 {5, 21}, 00565 {4, 22}, 00566 {10, 23}, 00567 {26, 24}, 00568 {17, 25}, 00569 {20, 26}, 00570 {16, 27}, 00571 {10, 28}, 00572 {19, 29}, 00573 {10, 30}, 00574 {10, 31}, 00575 {23, 32}, 00576 {22, 33}, 00577 {26, 34}, 00578 {27, 35}, 00579 {22, 36}, 00580 {27, 37}, 00581 {22, 38}, 00582 {22, 39}, 00583 {13, 40}, 00584 {14, 41}, 00585 {16, 27}, 00586 {26, 34}, 00587 {26, 42}, 00588 {27, 35}, 00589 {22, 36}, 00590 {20, 43}, 00591 {26, 24}, 00592 {22, 44}, 00593 {13, 45}, 00594 {19, 46}, 00595 {20, 47}, 00596 {16, 48}, 00597 {15, 49}, 00598 {17, 50}, 00599 {10, 28}, 00600 {20, 51}, 00601 {5, 52}, 00602 {26, 24}, 00603 {19, 53}, 00604 {15, 54}, 00605 {10, 55}, 00606 {10, 56}, 00607 {13, 57}, 00608 {13, 58}, 00609 {13, 59}, 00610 {12, 60}, 00611 {12, 61}, 00612 {18, 62}, 00613 {10, 63}, 00614 {18, 64}, 00615 {16, 65}, 00616 {20, 66}, 00617 {12, 67}, 00618 {6, 68}, 00619 {6, 68}, 00620 {15, 69}, 00621 {15, 70}, 00622 {15, 70}, 00623 {21, 71}, 00624 {30, 72}, 00625 {30, 73}, 00626 {30, 74}, 00627 {30, 75}, 00628 {23, 76}, 00629 {15, 77}, 00630 {15, 78}, 00631 {27, 79}, 00632 {27, 80}, 00633 {27, 81}, 00634 {27, 82}, 00635 {27, 83}, 00636 {27, 84}, 00637 {27, 79}, 00638 {27, 85}, 00639 {27, 86}, 00640 {10, 87}, 00641 {3, 88} 00642 }; 00643 00644 // STATISTICS: example-any