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 <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
00119 class SortByWeight {
00120 public:
00122 order_t orders;
00124 SortByWeight(order_t _orders) : orders(_orders) {}
00126 bool operator() (int i, int j) {
00127
00128
00129 return (orders[i][order_weight] > orders[j][order_weight]) ||
00130 (orders[i][order_weight] == orders[j][order_weight] && i<j);
00131 }
00132 };
00133
00162 class SteelMill : public IntMinimizeScript {
00163 protected:
00167 int* capacities;
00168 int ncapacities;
00169 int maxcapacity;
00170 int* loss;
00171 int ncolors;
00172 order_t orders;
00173 unsigned int norders;
00174 unsigned int nslabs;
00175
00176
00180 IntVarArray slab,
00181 slabload,
00182 slabcost;
00183 IntVar total_cost;
00184
00185
00186 public:
00188 enum {
00189 SYMMETRY_NONE,
00190 SYMMETRY_BRANCHING,
00191 SYMMETRY_LDSB
00192 };
00193
00195 SteelMill(const SteelMillOptions& opt)
00196 :
00197 capacities(opt.capacities()), ncapacities(opt.ncapacities()),
00198 maxcapacity(opt.maxcapacity()), loss(opt.loss()),
00199 ncolors(opt.ncolors()), orders(opt.orders()),
00200 norders(opt.size()), nslabs(opt.size()),
00201
00202 slab(*this, norders, 0,nslabs-1),
00203 slabload(*this, nslabs, 0,45),
00204 slabcost(*this, nslabs, 0, Int::Limits::max),
00205 total_cost(*this, 0, Int::Limits::max)
00206 {
00207
00208 BoolVarArgs boolslab(norders*nslabs);
00209 for (unsigned int i = 0; i < norders; ++i) {
00210 BoolVarArgs tmp(nslabs);
00211 for (int j = nslabs; j--; ) {
00212 boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1);
00213 }
00214 channel(*this, tmp, slab[i]);
00215 }
00216
00217
00218 for (unsigned int s = 0; s < nslabs; ++s) {
00219 IntArgs c(norders);
00220 BoolVarArgs x(norders);
00221 for (int i = norders; i--; ) {
00222 c[i] = orders[i][order_weight];
00223 x[i] = boolslab[s + i*nslabs];
00224 }
00225 linear(*this, c, x, IRT_EQ, slabload[s]);
00226 }
00227
00228 int totalweight = 0;
00229 for (unsigned int i = norders; i-- ; )
00230 totalweight += orders[i][order_weight] ;
00231 linear(*this, slabload, IRT_EQ, totalweight);
00232
00233
00234
00235 IntArgs nofcolor(ncolors);
00236 for (int c = ncolors; c--; ) {
00237 nofcolor[c] = 0;
00238 for (int o = norders; o--; ) {
00239 if (orders[o][order_color] == c) nofcolor[c] += 1;
00240 }
00241 }
00242 BoolVar f(*this, 0, 0);
00243 for (unsigned int s = 0; s < nslabs; ++s) {
00244 BoolVarArgs hascolor(ncolors);
00245 for (int c = ncolors; c--; ) {
00246 if (nofcolor[c]) {
00247 BoolVarArgs hasc(nofcolor[c]);
00248 int pos = 0;
00249 for (int o = norders; o--; ) {
00250 if (orders[o][order_color] == c)
00251 hasc[pos++] = boolslab[s + o*nslabs];
00252 }
00253 assert(pos == nofcolor[c]);
00254 hascolor[c] = BoolVar(*this, 0, 1);
00255 rel(*this, BOT_OR, hasc, hascolor[c]);
00256 } else {
00257 hascolor[c] = f;
00258 }
00259 }
00260 linear(*this, hascolor, IRT_LQ, 2);
00261 }
00262
00263
00264 IntArgs l(maxcapacity, loss);
00265 for (int s = nslabs; s--; ) {
00266 element(*this, l, slabload[s], slabcost[s]);
00267 }
00268 linear(*this, slabcost, IRT_EQ, total_cost);
00269
00270
00271 if (opt.symmetry() == SYMMETRY_BRANCHING) {
00272
00273 SteelMillBranch::post(*this);
00274 } else if (opt.symmetry() == SYMMETRY_NONE) {
00275 branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN());
00276 } else {
00277
00278 Symmetries syms;
00279 syms << ValueSymmetry(IntArgs::create(nslabs,0));
00280
00281
00282
00283
00284
00285 SortByWeight sbw(orders);
00286 IntArgs indices(norders);
00287 for (unsigned int i = 0 ; i < norders ; i++)
00288 indices[i] = i;
00289 Support::quicksort(&indices[0],norders,sbw);
00290 IntVarArgs sorted_orders(norders);
00291 for (unsigned int i = 0 ; i < norders ; i++) {
00292 sorted_orders[i] = slab[indices[i]];
00293 }
00294 branch(*this, sorted_orders, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
00295 }
00296 }
00297
00299 virtual void
00300 print(std::ostream& os) const {
00301 os << "What slab=" << slab << std::endl;
00302 os << "Slab load=" << slabload << std::endl;
00303 os << "Slab cost=" << slabcost << std::endl;
00304 os << "Total cost=" << total_cost << std::endl;
00305 int nslabsused = 0;
00306 int nslabscost = 0;
00307 bool unassigned = false;
00308 for (int i = nslabs; i--; ) {
00309 if (!slabload[i].assigned() || !slabcost[i].assigned()) {
00310 unassigned = true;
00311 break;
00312 }
00313 if (slabload[i].min()>0) ++nslabsused;
00314 if (slabcost[i].min()>0) ++nslabscost;
00315 }
00316 if (!unassigned)
00317 os << "Number of slabs used=" << nslabsused
00318 << ", slabs with cost=" << nslabscost
00319 << std::endl;
00320 os << std::endl;
00321 }
00322
00324 SteelMill(bool share, SteelMill& s)
00325 : IntMinimizeScript(share,s),
00326 capacities(s.capacities), ncapacities(s.ncapacities),
00327 maxcapacity(s.maxcapacity), loss(s.loss),
00328 ncolors(s.ncolors), orders(s.orders),
00329 norders(s.norders), nslabs(s.nslabs) {
00330 slab.update(*this, share, s.slab);
00331 slabload.update(*this, share, s.slabload);
00332 slabcost.update(*this, share, s.slabcost);
00333 total_cost.update(*this, share, s.total_cost);
00334 }
00336 virtual Space*
00337 copy(bool share) {
00338 return new SteelMill(share,*this);
00339 }
00341 virtual IntVar cost(void) const {
00342 return total_cost;
00343 }
00344
00345
00354 class SteelMillBranch : Brancher {
00355 protected:
00357 mutable int start;
00359 class Choice : public Gecode::Choice {
00360 public:
00362 int pos;
00364 int val;
00368 Choice(const Brancher& b, unsigned int a, int pos0, int val0)
00369 : Gecode::Choice(b,a), pos(pos0), val(val0) {}
00371 virtual size_t size(void) const {
00372 return sizeof(Choice);
00373 }
00375 virtual void archive(Archive& e) const {
00376 Gecode::Choice::archive(e);
00377 e << alternatives() << pos << val;
00378 }
00379 };
00380
00382 SteelMillBranch(Home home)
00383 : Brancher(home), start(0) {}
00385 SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
00386 : Brancher(home, share, b), start(b.start) {
00387 }
00388
00389 public:
00391 virtual bool status(const Space& home) const {
00392 const SteelMill& sm = static_cast<const SteelMill&>(home);
00393 for (unsigned int i = start; i < sm.norders; ++i)
00394 if (!sm.slab[i].assigned()) {
00395 start = i;
00396 return true;
00397 }
00398
00399 return false;
00400 }
00402 virtual Gecode::Choice* choice(Space& home) {
00403 SteelMill& sm = static_cast<SteelMill&>(home);
00404 assert(!sm.slab[start].assigned());
00405
00406 unsigned int size = sm.norders;
00407 int weight = 0;
00408 unsigned int pos = start;
00409 for (unsigned int i = start; i<sm.norders; ++i) {
00410 if (!sm.slab[i].assigned()) {
00411 if (sm.slab[i].size() == size &&
00412 sm.orders[i][order_weight] > weight) {
00413 weight = sm.orders[i][order_weight];
00414 pos = i;
00415 } else if (sm.slab[i].size() < size) {
00416 size = sm.slab[i].size();
00417 weight = sm.orders[i][order_weight];
00418 pos = i;
00419 }
00420 }
00421 }
00422 unsigned int val = sm.slab[pos].min();
00423
00424 unsigned int firstzero = 0;
00425 while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
00426 ++firstzero;
00427 assert(pos < sm.nslabs &&
00428 val < sm.norders);
00429 return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
00430 }
00431 virtual Choice* choice(const Space&, Archive& e) {
00432 unsigned int alt; int pos, val;
00433 e >> alt >> pos >> val;
00434 return new Choice(*this, alt, pos, val);
00435 }
00437 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00438 unsigned int a) {
00439 SteelMill& sm = static_cast<SteelMill&>(home);
00440 const Choice& c = static_cast<const Choice&>(_c);
00441 if (a)
00442 return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
00443 ? ES_FAILED : ES_OK;
00444 else
00445 return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
00446 ? ES_FAILED : ES_OK;
00447 }
00449 virtual void print(const Space&, const Gecode::Choice& _c,
00450 unsigned int a,
00451 std::ostream& o) const {
00452 const Choice& c = static_cast<const Choice&>(_c);
00453 o << "slab[" << c.pos << "] "
00454 << ((a == 0) ? "=" : "!=")
00455 << " " << c.val;
00456 }
00458 virtual Actor* copy(Space& home, bool share) {
00459 return new (home) SteelMillBranch(home, share, *this);
00460 }
00462 static BrancherHandle post(Home home) {
00463 return *new (home) SteelMillBranch(home);
00464 }
00466 virtual size_t dispose(Space&) {
00467 return sizeof(*this);
00468 }
00469 };
00470 };
00471
00475 int
00476 main(int argc, char* argv[]) {
00477 SteelMillOptions opt("Steel Mill Slab design");
00478 opt.symmetry(SteelMill::SYMMETRY_BRANCHING);
00479 opt.symmetry(SteelMill::SYMMETRY_NONE,"none");
00480 opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
00481 opt.symmetry(SteelMill::SYMMETRY_LDSB,"ldsb");
00482 opt.solutions(0);
00483 if (!opt.parse(argc,argv))
00484 return 1;
00485 Script::run<SteelMill,BAB,SteelMillOptions>(opt);
00486 return 0;
00487 }
00488
00489
00490 void
00491 SteelMillOptions::help(void) {
00492 Options::help();
00493 std::cerr << "\t(string), optional" << std::endl
00494 << "\t\tBenchmark to load." << std::endl
00495 << "\t\tIf none is given, the standard CSPLib instance is used."
00496 << std::endl;
00497 std::cerr << "\t(unsigned int), optional" << std::endl
00498 << "\t\tNumber of orders to use, in the interval [0..norders]."
00499 << std::endl
00500 << "\t\tIf none is given, all orders are used." << std::endl;
00501 }
00502
00503 bool
00504 SteelMillOptions::parse(int& argc, char* argv[]) {
00505 Options::parse(argc,argv);
00506
00507 if (argc >= 4) {
00508 std::cerr << "Too many arguments given, max two allowed (given={";
00509 for (int i = 1; i < argc; ++i) {
00510 std::cerr << "\"" << argv[i] << "\"";
00511 if (i < argc-1) std::cerr << ",";
00512 }
00513 std::cerr << "})." << std::endl;
00514 return false;
00515 }
00516
00517 while (argc >= 2) {
00518 bool issize = true;
00519 for (int i = strlen(argv[argc-1]); i-- && issize; )
00520 issize &= (isdigit(argv[argc-1][i]) != 0);
00521 if (issize) {
00522 _size = atoi(argv[argc-1]);
00523 } else {
00524 std::ifstream instance(argv[argc-1]);
00525 if (instance.fail()) {
00526 std::cerr << "Argument \"" << argv[argc-1]
00527 << "\" is neither an integer nor a readable file"
00528 << std::endl;
00529 return false;
00530 }
00531
00532 instance >> _ncapacities;
00533 _capacities = new int[_ncapacities];
00534 _maxcapacity = -1;
00535 for (int i = 0; i < _ncapacities; ++i) {
00536 instance >> _capacities[i];
00537 _maxcapacity = std::max(_maxcapacity, _capacities[i]);
00538 }
00539 instance >> _ncolors >> _norders;
00540 _orders = new int[_norders][2];
00541 for (unsigned int i = 0; i < _norders; ++i) {
00542 instance >> _orders[i][order_weight] >> _orders[i][order_color];
00543 }
00544 }
00545
00546 --argc;
00547 }
00548
00549 {
00550 _loss = new int[_maxcapacity+1];
00551 _loss[0] = 0;
00552 int currcap = 0;
00553 for (int c = 1; c < _maxcapacity; ++c) {
00554 if (c > _capacities[currcap]) ++currcap;
00555 _loss[c] = _capacities[currcap] - c;
00556 }
00557 }
00558
00559 if (_size == 0) {
00560 _size = _norders;
00561 }
00562
00563 if (_size == 0 || _size > _norders) {
00564 std::cerr << "Size must be between 1 and " << _norders << std::endl;
00565 return false;
00566 }
00567 return true;
00568 }
00569
00570
00571 const int order_weight = 0;
00572 const int order_color = 1;
00573
00574
00575 int csplib_capacities[] =
00576 {12, 14, 17, 18, 19,
00577 20, 23, 24, 25, 26,
00578 27, 28, 29, 30, 32,
00579 35, 39, 42, 43, 44};
00580 unsigned int csplib_ncapacities = 20;
00581 unsigned int csplib_maxcapacity = 44;
00582 int csplib_loss[45];
00583 unsigned int csplib_ncolors = 89;
00584 unsigned int csplib_norders = 111;
00585 int csplib_orders[][2] = {
00586 {4, 1},
00587 {22, 2},
00588 {9, 3},
00589 {5, 4},
00590 {8, 5},
00591 {3, 6},
00592 {3, 4},
00593 {4, 7},
00594 {7, 4},
00595 {7, 8},
00596 {3, 6},
00597 {2, 6},
00598 {2, 4},
00599 {8, 9},
00600 {5, 10},
00601 {7, 11},
00602 {4, 7},
00603 {7, 11},
00604 {5, 10},
00605 {7, 11},
00606 {8, 9},
00607 {3, 1},
00608 {25, 12},
00609 {14, 13},
00610 {3, 6},
00611 {22, 14},
00612 {19, 15},
00613 {19, 15},
00614 {22, 16},
00615 {22, 17},
00616 {22, 18},
00617 {20, 19},
00618 {22, 20},
00619 {5, 21},
00620 {4, 22},
00621 {10, 23},
00622 {26, 24},
00623 {17, 25},
00624 {20, 26},
00625 {16, 27},
00626 {10, 28},
00627 {19, 29},
00628 {10, 30},
00629 {10, 31},
00630 {23, 32},
00631 {22, 33},
00632 {26, 34},
00633 {27, 35},
00634 {22, 36},
00635 {27, 37},
00636 {22, 38},
00637 {22, 39},
00638 {13, 40},
00639 {14, 41},
00640 {16, 27},
00641 {26, 34},
00642 {26, 42},
00643 {27, 35},
00644 {22, 36},
00645 {20, 43},
00646 {26, 24},
00647 {22, 44},
00648 {13, 45},
00649 {19, 46},
00650 {20, 47},
00651 {16, 48},
00652 {15, 49},
00653 {17, 50},
00654 {10, 28},
00655 {20, 51},
00656 {5, 52},
00657 {26, 24},
00658 {19, 53},
00659 {15, 54},
00660 {10, 55},
00661 {10, 56},
00662 {13, 57},
00663 {13, 58},
00664 {13, 59},
00665 {12, 60},
00666 {12, 61},
00667 {18, 62},
00668 {10, 63},
00669 {18, 64},
00670 {16, 65},
00671 {20, 66},
00672 {12, 67},
00673 {6, 68},
00674 {6, 68},
00675 {15, 69},
00676 {15, 70},
00677 {15, 70},
00678 {21, 71},
00679 {30, 72},
00680 {30, 73},
00681 {30, 74},
00682 {30, 75},
00683 {23, 76},
00684 {15, 77},
00685 {15, 78},
00686 {27, 79},
00687 {27, 80},
00688 {27, 81},
00689 {27, 82},
00690 {27, 83},
00691 {27, 84},
00692 {27, 79},
00693 {27, 85},
00694 {27, 86},
00695 {10, 87},
00696 {3, 88}
00697 };
00698
00699