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 }
00339 };
00340
00342 SteelMillBranch(Space& 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
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
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
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(Space& home) {
00409 (void) new (home) SteelMillBranch(home);
00410 }
00412 virtual size_t dispose(Space& home) {
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
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
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
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
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
00504 if (_size == 0) {
00505 _size = _norders;
00506 }
00507
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
00516 const int order_weight = 0;
00517 const int order_color = 1;
00518
00519
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