Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
20 kB · 692 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Mikael Lagerkvist <lagerkvist@gecode.org> * * Copyright: * Mikael Lagerkvist, 2008 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <gecode/driver.hh>#include <gecode/int.hh>#include <gecode/minimodel.hh>
#include <fstream>
using namespace Gecode;
/** \brief Order-specifications * * Used in the \ref SteelMill example. * *///@{typedef int (*order_t)[2]; ///< Type of the order-specificationextern const int order_weight; ///< Weight-position in order-array elementsextern const int order_color; ///< Color-position in order-array elements//@}
/** \brief Constants for CSPLib instance of the Steel Mill Slab Design Problem. * * Used in the \ref SteelMill example. *///@{extern int csplib_capacities[]; ///< Capacitiesextern unsigned int csplib_ncapacities; ///< Number of capacitiesextern unsigned int csplib_maxcapacity; ///< Maximum capacityextern int csplib_loss[]; ///< Loss for all sizesextern int csplib_orders[][2]; ///< Ordersextern unsigned int csplib_ncolors; ///< Number of colorsextern unsigned int csplib_norders; ///< Number of orders//@}
/** \brief %SteelMillOptions for examples with size option and an additional * optional file name parameter. * * Used in the \ref SteelMill example. */class SteelMillOptions : public Options {private: unsigned int _size; ///< Size value int* _capacities; ///< Capacities int _ncapacities; ///< Number of capacities int _maxcapacity; ///< Maximum capacity int* _loss; ///< Loss for all sizes order_t _orders; ///< Orders int _ncolors; ///< Number of colors unsigned int _norders; ///< Number of orderspublic: /// Initialize options for example with name \a n SteelMillOptions(const char* n) : Options(n), _size(csplib_norders), _capacities(csplib_capacities), _ncapacities(csplib_ncapacities), _maxcapacity(csplib_maxcapacity), _loss(csplib_loss), _orders(&(csplib_orders[0])), _ncolors(csplib_ncolors), _norders(csplib_norders) {} /// Print help text virtual void help(void); /// Parse options from arguments \a argv (number is \a argc) bool parse(int& argc, char* argv[]);
/// Return size unsigned int size(void) const { return _size; } /// Return capacities int* capacities(void) const { return _capacities; } /// Return number of capacities int ncapacities(void) const { return _ncapacities; } /// Return maximum of capacities int maxcapacity(void) const { return _maxcapacity; } /// Return loss values int* loss(void) const { return _loss; } /// Return orders order_t orders(void) const { return _orders; } /// Return number of colors int ncolors(void) const { return _ncolors; } /// Return number of orders int norders(void) const { return _norders; }};
/// Sort orders by weightclass SortByWeight {public: /// The orders order_t orders; /// Initialize orders SortByWeight(order_t _orders) : orders(_orders) {} /// Sort order bool operator() (int i, int j) { // Order i comes before order j if the weight of i is larger than // the weight of j. return (orders[i][order_weight] > orders[j][order_weight]) || (orders[i][order_weight] == orders[j][order_weight] && i<j); }};
/** * \brief %Example: Steel-mill slab design problem * * This model solves the Steel Mill Slab Design Problem (Problem 38 in * <a href="http://csplib.org">CSPLib</a>). The model is from Gargani * and Refalo, "An efficient model and strategy for the steel mill * slab design problem.", CP 2007, except that a decomposition of the * packing constraint is used. The symmetry-breaking search is from * Van Hentenryck and Michel, "The Steel Mill Slab Design Problem * Revisited", CPAIOR 2008. * * The program accepts an optional argument for a data-file containing * an instance of the problem. The format for the data-file is the following: * <pre> * "number of slab capacities" "sequence of capacities in increasing order" * "number of colors" * "number of orders" * "size order 1" "color of order 1" * "size order 2" "color of order 2" * ... * </pre> * Hard instances are available from <a href= * "http://becool.info.ucl.ac.be/steelmillslab"> * http://becool.info.ucl.ac.be/steelmillslab</a>. * * \ingroup Example * */class SteelMill : public IntMinimizeScript {protected: /** \name Instance specification */ //@{ int* capacities; ///< Capacities int ncapacities; ///< Number of capacities int maxcapacity; ///< Maximum capacity int* loss; ///< Loss for all sizes int ncolors; ///< Number of colors order_t orders; ///< Orders unsigned int norders; ///< Number of orders unsigned int nslabs; ///< Number of slabs //@}
/** \name Problem variables */ //@{ IntVarArray slab, ///< Slab assigned to order i slabload, ///< Load of slab j slabcost; ///< Cost of slab j IntVar total_cost; ///< Total cost //@}
public: /// Branching variants enum { SYMMETRY_NONE, ///< Simple symmetry SYMMETRY_BRANCHING, ///< Breaking symmetries with symmetry SYMMETRY_LDSB ///< Use LDSB for symmetry breaking };
/// Actual model SteelMill(const SteelMillOptions& opt) : // Initialize instance data IntMinimizeScript(opt), capacities(opt.capacities()), ncapacities(opt.ncapacities()), maxcapacity(opt.maxcapacity()), loss(opt.loss()), ncolors(opt.ncolors()), orders(opt.orders()), norders(opt.size()), nslabs(opt.size()), // Initialize problem variables slab(*this, norders, 0,nslabs-1), slabload(*this, nslabs, 0,45), slabcost(*this, nslabs, 0, Int::Limits::max), total_cost(*this, 0, Int::Limits::max) { // Boolean variables for slab[o]==s BoolVarArgs boolslab(norders*nslabs); for (unsigned int i = 0; i < norders; ++i) { BoolVarArgs tmp(nslabs); for (int j = nslabs; j--; ) { boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1); } channel(*this, tmp, slab[i]); }
// Packing constraints for (unsigned int s = 0; s < nslabs; ++s) { IntArgs c(norders); BoolVarArgs x(norders); for (int i = norders; i--; ) { c[i] = orders[i][order_weight]; x[i] = boolslab[s + i*nslabs]; } linear(*this, c, x, IRT_EQ, slabload[s]); } // Redundant packing constraint int totalweight = 0; for (unsigned int i = norders; i-- ; ) totalweight += orders[i][order_weight] ; linear(*this, slabload, IRT_EQ, totalweight);
// Color constraints IntArgs nofcolor(ncolors); for (int c = ncolors; c--; ) { nofcolor[c] = 0; for (int o = norders; o--; ) { if (orders[o][order_color] == c) nofcolor[c] += 1; } } BoolVar f(*this, 0, 0); for (unsigned int s = 0; s < nslabs; ++s) { BoolVarArgs hascolor(ncolors); for (int c = ncolors; c--; ) { if (nofcolor[c]) { BoolVarArgs hasc(nofcolor[c]); int pos = 0; for (int o = norders; o--; ) { if (orders[o][order_color] == c) hasc[pos++] = boolslab[s + o*nslabs]; } assert(pos == nofcolor[c]); hascolor[c] = BoolVar(*this, 0, 1); rel(*this, BOT_OR, hasc, hascolor[c]); } else { hascolor[c] = f; } } linear(*this, hascolor, IRT_LQ, 2); }
// Compute slabcost IntArgs l(maxcapacity, loss); for (int s = nslabs; s--; ) { element(*this, l, slabload[s], slabcost[s]); } linear(*this, slabcost, IRT_EQ, total_cost);
// Add branching if (opt.symmetry() == SYMMETRY_BRANCHING) { // Symmetry breaking branching SteelMillBranch::post(*this); } else if (opt.symmetry() == SYMMETRY_NONE) { branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN()); } else { // opt.symmetry() == SYMMETRY_LDSB // There is one symmetry: the values (slabs) are interchangeable. Symmetries syms; syms << ValueSymmetry(IntArgs::create(nslabs,0));
// For variable order we mimic the custom brancher. We use // min-size domain, breaking ties by maximum weight (preferring // to label larger weights earlier). To do this, we first sort // (stably) by maximum weight, then use min-size domain. SortByWeight sbw(orders); IntArgs indices(norders); for (unsigned int i = 0 ; i < norders ; i++) indices[i] = i; Support::quicksort(&indices[0],norders,sbw); IntVarArgs sorted_orders(norders); for (unsigned int i = 0 ; i < norders ; i++) { sorted_orders[i] = slab[indices[i]]; } branch(*this, sorted_orders, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms); } }
/// Print solution virtual void print(std::ostream& os) const { os << "What slab=" << slab << std::endl; os << "Slab load=" << slabload << std::endl; os << "Slab cost=" << slabcost << std::endl; os << "Total cost=" << total_cost << std::endl; int nslabsused = 0; int nslabscost = 0; bool unassigned = false; for (int i = nslabs; i--; ) { if (!slabload[i].assigned() || !slabcost[i].assigned()) { unassigned = true; break; } if (slabload[i].min()>0) ++nslabsused; if (slabcost[i].min()>0) ++nslabscost; } if (!unassigned) os << "Number of slabs used=" << nslabsused << ", slabs with cost=" << nslabscost << std::endl; os << std::endl; }
/// Constructor for cloning \a s SteelMill(SteelMill& s) : IntMinimizeScript(s), capacities(s.capacities), ncapacities(s.ncapacities), maxcapacity(s.maxcapacity), loss(s.loss), ncolors(s.ncolors), orders(s.orders), norders(s.norders), nslabs(s.nslabs) { slab.update(*this, s.slab); slabload.update(*this, s.slabload); slabcost.update(*this, s.slabcost); total_cost.update(*this, s.total_cost); } /// Copy during cloning virtual Space* copy(void) { return new SteelMill(*this); } /// Return solution cost virtual IntVar cost(void) const { return total_cost; }
/** \brief Custom brancher for steel mill slab design * * This class implements a custom brancher for SteelMill that * considers all slabs with no order assigned to it currently to be * symmetric. * * \relates SteelMill */ class SteelMillBranch : Brancher { protected: /// Cache of first unassigned value mutable int start; /// %Choice class Choice : public Gecode::Choice { public: /// Position of variable int pos; /// Value of variable int val; /** Initialize choice for brancher \a b, number of * alternatives \a a, position \a pos0, and value \a val0. */ Choice(const Brancher& b, unsigned int a, int pos0, int val0) : Gecode::Choice(b,a), pos(pos0), val(val0) {} /// Archive into \a e virtual void archive(Archive& e) const { Gecode::Choice::archive(e); e << alternatives() << pos << val; } };
/// Construct brancher SteelMillBranch(Home home) : Brancher(home), start(0) {} /// Copy constructor SteelMillBranch(Space& home, SteelMillBranch& b) : Brancher(home, b), start(b.start) { }
public: /// Check status of brancher, return true if alternatives left. virtual bool status(const Space& home) const { const SteelMill& sm = static_cast<const SteelMill&>(home); for (unsigned int i = start; i < sm.norders; ++i) if (!sm.slab[i].assigned()) { start = i; return true; } // No non-assigned orders left return false; } /// Return choice virtual Gecode::Choice* choice(Space& home) { SteelMill& sm = static_cast<SteelMill&>(home); assert(!sm.slab[start].assigned()); // Find order with a) minimum size, b) largest weight unsigned int size = sm.norders; int weight = 0; unsigned int pos = start; for (unsigned int i = start; i<sm.norders; ++i) { if (!sm.slab[i].assigned()) { if (sm.slab[i].size() == size && sm.orders[i][order_weight] > weight) { weight = sm.orders[i][order_weight]; pos = i; } else if (sm.slab[i].size() < size) { size = sm.slab[i].size(); weight = sm.orders[i][order_weight]; pos = i; } } } unsigned int val = sm.slab[pos].min(); // Find first still empty slab (all such slabs are symmetric) unsigned int firstzero = 0; while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0) ++firstzero; assert(pos < sm.nslabs && val < sm.norders); return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val); } virtual Choice* choice(const Space&, Archive& e) { unsigned int alt; int pos, val; e >> alt >> pos >> val; return new Choice(*this, alt, pos, val); } /// Perform commit for choice \a _c and alternative \a a virtual ExecStatus commit(Space& home, const Gecode::Choice& _c, unsigned int a) { SteelMill& sm = static_cast<SteelMill&>(home); const Choice& c = static_cast<const Choice&>(_c); if (a) return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val)) ? ES_FAILED : ES_OK; else return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val)) ? ES_FAILED : ES_OK; } /// Print explanation virtual void print(const Space&, const Gecode::Choice& _c, unsigned int a, std::ostream& o) const { const Choice& c = static_cast<const Choice&>(_c); o << "slab[" << c.pos << "] " << ((a == 0) ? "=" : "!=") << " " << c.val; } /// Copy brancher virtual Actor* copy(Space& home) { return new (home) SteelMillBranch(home, *this); } /// Post brancher static void post(Home home) { (void) new (home) SteelMillBranch(home); } /// Delete brancher and return its size virtual size_t dispose(Space&) { return sizeof(*this); } };};
/** \brief Main-function * \relates SteelMill */intmain(int argc, char* argv[]) { SteelMillOptions opt("Steel Mill Slab design"); opt.symmetry(SteelMill::SYMMETRY_BRANCHING); opt.symmetry(SteelMill::SYMMETRY_NONE,"none"); opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching"); opt.symmetry(SteelMill::SYMMETRY_LDSB,"ldsb"); opt.solutions(0); if (!opt.parse(argc,argv)) return 1; Script::run<SteelMill,BAB,SteelMillOptions>(opt); return 0;}
voidSteelMillOptions::help(void) { Options::help(); std::cerr << "\t(string), optional" << std::endl << "\t\tBenchmark to load." << std::endl << "\t\tIf none is given, the standard CSPLib instance is used." << std::endl; std::cerr << "\t(unsigned int), optional" << std::endl << "\t\tNumber of orders to use, in the interval [0..norders]." << std::endl << "\t\tIf none is given, all orders are used." << std::endl;}
boolSteelMillOptions::parse(int& argc, char* argv[]) { Options::parse(argc,argv); // Check number of arguments if (argc >= 4) { std::cerr << "Too many arguments given, max two allowed (given={"; for (int i = 1; i < argc; ++i) { std::cerr << "\"" << argv[i] << "\""; if (i < argc-1) std::cerr << ","; } std::cerr << "})." << std::endl; return false; } // Parse options while (argc >= 2) { bool issize = true; for (int i = strlen(argv[argc-1]); i-- && issize; ) issize &= (isdigit(argv[argc-1][i]) != 0); if (issize) { _size = atoi(argv[argc-1]); } else { std::ifstream instance(argv[argc-1]); if (instance.fail()) { std::cerr << "Argument \"" << argv[argc-1] << "\" is neither an integer nor a readable file" << std::endl; return false; } // Read file instance instance >> _ncapacities; _capacities = new int[_ncapacities]; _maxcapacity = -1; for (int i = 0; i < _ncapacities; ++i) { instance >> _capacities[i]; _maxcapacity = std::max(_maxcapacity, _capacities[i]); } instance >> _ncolors >> _norders; _orders = new int[_norders][2]; for (unsigned int i = 0; i < _norders; ++i) { instance >> _orders[i][order_weight] >> _orders[i][order_color]; } }
--argc; } // Compute loss { _loss = new int[_maxcapacity+1]; _loss[0] = 0; int currcap = 0; for (int c = 1; c < _maxcapacity; ++c) { if (c > _capacities[currcap]) ++currcap; _loss[c] = _capacities[currcap] - c; } } // Set size, if none given if (_size == 0) { _size = _norders; } // Check size reasonability if (_size == 0 || _size > _norders) { std::cerr << "Size must be between 1 and " << _norders << std::endl; return false; } return true;}
// Positions in order arrayconst int order_weight = 0;const int order_color = 1;
// CSPLib instanceint csplib_capacities[] = {12, 14, 17, 18, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 32, 35, 39, 42, 43, 44};unsigned int csplib_ncapacities = 20;unsigned int csplib_maxcapacity = 44;int csplib_loss[45];unsigned int csplib_ncolors = 89;unsigned int csplib_norders = 111;int csplib_orders[][2] = { {4, 1}, {22, 2}, {9, 3}, {5, 4}, {8, 5}, {3, 6}, {3, 4}, {4, 7}, {7, 4}, {7, 8}, {3, 6}, {2, 6}, {2, 4}, {8, 9}, {5, 10}, {7, 11}, {4, 7}, {7, 11}, {5, 10}, {7, 11}, {8, 9}, {3, 1}, {25, 12}, {14, 13}, {3, 6}, {22, 14}, {19, 15}, {19, 15}, {22, 16}, {22, 17}, {22, 18}, {20, 19}, {22, 20}, {5, 21}, {4, 22}, {10, 23}, {26, 24}, {17, 25}, {20, 26}, {16, 27}, {10, 28}, {19, 29}, {10, 30}, {10, 31}, {23, 32}, {22, 33}, {26, 34}, {27, 35}, {22, 36}, {27, 37}, {22, 38}, {22, 39}, {13, 40}, {14, 41}, {16, 27}, {26, 34}, {26, 42}, {27, 35}, {22, 36}, {20, 43}, {26, 24}, {22, 44}, {13, 45}, {19, 46}, {20, 47}, {16, 48}, {15, 49}, {17, 50}, {10, 28}, {20, 51}, {5, 52}, {26, 24}, {19, 53}, {15, 54}, {10, 55}, {10, 56}, {13, 57}, {13, 58}, {13, 59}, {12, 60}, {12, 61}, {18, 62}, {10, 63}, {18, 64}, {16, 65}, {20, 66}, {12, 67}, {6, 68}, {6, 68}, {15, 69}, {15, 70}, {15, 70}, {21, 71}, {30, 72}, {30, 73}, {30, 74}, {30, 75}, {23, 76}, {15, 77}, {15, 78}, {27, 79}, {27, 80}, {27, 81}, {27, 82}, {27, 83}, {27, 84}, {27, 79}, {27, 85}, {27, 86}, {10, 87}, {3, 88}};
// STATISTICS: example-any