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