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