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
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 :
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
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
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
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
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
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
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
00255 if (opt.symmetry() == SYMMETRY_BRANCHING) {
00256
00257 SteelMillBranch::post(*this);
00258 } else {
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 }
00340 virtual void archive(Archive& e) const {
00341 Gecode::Choice::archive(e);
00342 e << alternatives() << pos << val;
00343 }
00344 };
00345
00347 SteelMillBranch(Home home)
00348 : Brancher(home), start(0) {}
00350 SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
00351 : Brancher(home, share, b), start(b.start) {
00352 }
00353
00354 public:
00356 virtual bool status(const Space& home) const {
00357 const SteelMill& sm = static_cast<const SteelMill&>(home);
00358 for (unsigned int i = start; i < sm.norders; ++i)
00359 if (!sm.slab[i].assigned()) {
00360 start = i;
00361 return true;
00362 }
00363
00364 return false;
00365 }
00367 virtual Gecode::Choice* choice(Space& home) {
00368 SteelMill& sm = static_cast<SteelMill&>(home);
00369 assert(!sm.slab[start].assigned());
00370
00371 unsigned int size = sm.norders;
00372 int weight = 0;
00373 unsigned int pos = start;
00374 for (unsigned int i = start; i<sm.norders; ++i) {
00375 if (!sm.slab[i].assigned()) {
00376 if (sm.slab[i].size() == size &&
00377 sm.orders[i][order_weight] > weight) {
00378 weight = sm.orders[i][order_weight];
00379 pos = i;
00380 } else if (sm.slab[i].size() < size) {
00381 size = sm.slab[i].size();
00382 weight = sm.orders[i][order_weight];
00383 pos = i;
00384 }
00385 }
00386 }
00387 unsigned int val = sm.slab[pos].min();
00388
00389 unsigned int firstzero = 0;
00390 while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
00391 ++firstzero;
00392 assert(pos < sm.nslabs &&
00393 val < sm.norders);
00394 return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
00395 }
00396 virtual Choice* choice(const Space&, Archive& e) {
00397 unsigned int alt; int pos, val;
00398 e >> alt >> pos >> val;
00399 return new Choice(*this, alt, pos, val);
00400 }
00402 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00403 unsigned int a) {
00404 SteelMill& sm = static_cast<SteelMill&>(home);
00405 const Choice& c = static_cast<const Choice&>(_c);
00406 if (a)
00407 return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
00408 ? ES_FAILED : ES_OK;
00409 else
00410 return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
00411 ? ES_FAILED : ES_OK;
00412 }
00414 virtual Actor* copy(Space& home, bool share) {
00415 return new (home) SteelMillBranch(home, share, *this);
00416 }
00418 static void post(Home home) {
00419 (void) new (home) SteelMillBranch(home);
00420 }
00422 virtual size_t dispose(Space&) {
00423 return sizeof(*this);
00424 }
00425 };
00426 };
00427
00431 int
00432 main(int argc, char* argv[]) {
00433 SteelMillOptions opt("Steel Mill Slab design");
00434 opt.symmetry(SteelMill::SYMMETRY_BRANCHING);
00435 opt.symmetry(SteelMill::SYMMETRY_NONE,"none");
00436 opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
00437 opt.solutions(0);
00438 if (!opt.parse(argc,argv))
00439 return 1;
00440 Script::run<SteelMill,BAB,SteelMillOptions>(opt);
00441 return 0;
00442 }
00443
00444
00445 void
00446 SteelMillOptions::help(void) {
00447 Options::help();
00448 std::cerr << "\t(string), optional" << std::endl
00449 << "\t\tBenchmark to load." << std::endl
00450 << "\t\tIf none is given, the standard CSPLib instance is used."
00451 << std::endl;
00452 std::cerr << "\t(unsigned int), optional" << std::endl
00453 << "\t\tNumber of orders to use, in the interval [0..norders]."
00454 << std::endl
00455 << "\t\tIf none is given, all orders are used." << std::endl;
00456 }
00457
00458 bool
00459 SteelMillOptions::parse(int& argc, char* argv[]) {
00460 Options::parse(argc,argv);
00461
00462 if (argc >= 4) {
00463 std::cerr << "Too many arguments given, max two allowed (given={";
00464 for (int i = 1; i < argc; ++i) {
00465 std::cerr << "\"" << argv[i] << "\"";
00466 if (i < argc-1) std::cerr << ",";
00467 }
00468 std::cerr << "})." << std::endl;
00469 return false;
00470 }
00471
00472 while (argc >= 2) {
00473 bool issize = true;
00474 for (int i = strlen(argv[argc-1]); i-- && issize; )
00475 issize &= (isdigit(argv[argc-1][i]) != 0);
00476 if (issize) {
00477 _size = atoi(argv[argc-1]);
00478 } else {
00479 std::ifstream instance(argv[argc-1]);
00480 if (instance.fail()) {
00481 std::cerr << "Argument \"" << argv[argc-1]
00482 << "\" is neither an integer nor a readable file"
00483 << std::endl;
00484 return false;
00485 }
00486
00487 instance >> _ncapacities;
00488 _capacities = new int[_ncapacities];
00489 _maxcapacity = -1;
00490 for (int i = 0; i < _ncapacities; ++i) {
00491 instance >> _capacities[i];
00492 _maxcapacity = std::max(_maxcapacity, _capacities[i]);
00493 }
00494 instance >> _ncolors >> _norders;
00495 _orders = new int[_norders][2];
00496 for (unsigned int i = 0; i < _norders; ++i) {
00497 instance >> _orders[i][order_weight] >> _orders[i][order_color];
00498 }
00499 }
00500
00501 --argc;
00502 }
00503
00504 {
00505 _loss = new int[_maxcapacity+1];
00506 _loss[0] = 0;
00507 int currcap = 0;
00508 for (int c = 1; c < _maxcapacity; ++c) {
00509 if (c > _capacities[currcap]) ++currcap;
00510 _loss[c] = _capacities[currcap] - c;
00511 }
00512 }
00513
00514 if (_size == 0) {
00515 _size = _norders;
00516 }
00517
00518 if (_size == 0 || _size > _norders) {
00519 std::cerr << "Size must be between 1 and " << _norders << std::endl;
00520 return false;
00521 }
00522 return true;
00523 }
00524
00525
00526 const int order_weight = 0;
00527 const int order_color = 1;
00528
00529
00530 int csplib_capacities[] =
00531 {12, 14, 17, 18, 19,
00532 20, 23, 24, 25, 26,
00533 27, 28, 29, 30, 32,
00534 35, 39, 42, 43, 44};
00535 unsigned int csplib_ncapacities = 20;
00536 unsigned int csplib_maxcapacity = 44;
00537 int csplib_loss[45];
00538 unsigned int csplib_ncolors = 89;
00539 unsigned int csplib_norders = 111;
00540 int csplib_orders[][2] = {
00541 {4, 1},
00542 {22, 2},
00543 {9, 3},
00544 {5, 4},
00545 {8, 5},
00546 {3, 6},
00547 {3, 4},
00548 {4, 7},
00549 {7, 4},
00550 {7, 8},
00551 {3, 6},
00552 {2, 6},
00553 {2, 4},
00554 {8, 9},
00555 {5, 10},
00556 {7, 11},
00557 {4, 7},
00558 {7, 11},
00559 {5, 10},
00560 {7, 11},
00561 {8, 9},
00562 {3, 1},
00563 {25, 12},
00564 {14, 13},
00565 {3, 6},
00566 {22, 14},
00567 {19, 15},
00568 {19, 15},
00569 {22, 16},
00570 {22, 17},
00571 {22, 18},
00572 {20, 19},
00573 {22, 20},
00574 {5, 21},
00575 {4, 22},
00576 {10, 23},
00577 {26, 24},
00578 {17, 25},
00579 {20, 26},
00580 {16, 27},
00581 {10, 28},
00582 {19, 29},
00583 {10, 30},
00584 {10, 31},
00585 {23, 32},
00586 {22, 33},
00587 {26, 34},
00588 {27, 35},
00589 {22, 36},
00590 {27, 37},
00591 {22, 38},
00592 {22, 39},
00593 {13, 40},
00594 {14, 41},
00595 {16, 27},
00596 {26, 34},
00597 {26, 42},
00598 {27, 35},
00599 {22, 36},
00600 {20, 43},
00601 {26, 24},
00602 {22, 44},
00603 {13, 45},
00604 {19, 46},
00605 {20, 47},
00606 {16, 48},
00607 {15, 49},
00608 {17, 50},
00609 {10, 28},
00610 {20, 51},
00611 {5, 52},
00612 {26, 24},
00613 {19, 53},
00614 {15, 54},
00615 {10, 55},
00616 {10, 56},
00617 {13, 57},
00618 {13, 58},
00619 {13, 59},
00620 {12, 60},
00621 {12, 61},
00622 {18, 62},
00623 {10, 63},
00624 {18, 64},
00625 {16, 65},
00626 {20, 66},
00627 {12, 67},
00628 {6, 68},
00629 {6, 68},
00630 {15, 69},
00631 {15, 70},
00632 {15, 70},
00633 {21, 71},
00634 {30, 72},
00635 {30, 73},
00636 {30, 74},
00637 {30, 75},
00638 {23, 76},
00639 {15, 77},
00640 {15, 78},
00641 {27, 79},
00642 {27, 80},
00643 {27, 81},
00644 {27, 82},
00645 {27, 83},
00646 {27, 84},
00647 {27, 79},
00648 {27, 85},
00649 {27, 86},
00650 {10, 87},
00651 {3, 88}
00652 };
00653
00654