Generated on Fri Oct 19 11:24:49 2018 for Gecode by doxygen 1.6.3

steel-mill.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Mikael Lagerkvist, 2008
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Order i comes before order j if the weight of i is larger than
00124     // the weight of j.
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     : // Initialize instance data
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       // Initialize problem variables
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     // Boolean variables for slab[o]==s
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     // Packing constraints
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     // Redundant packing constraint
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     // Color constraints
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     // Compute slabcost
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     // Add branching
00268     if (opt.symmetry() == SYMMETRY_BRANCHING) {
00269       // Symmetry breaking branching
00270       SteelMillBranch::post(*this);
00271     } else if (opt.symmetry() == SYMMETRY_NONE) {
00272       branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN());
00273     } else { // opt.symmetry() == SYMMETRY_LDSB
00274       // There is one symmetry: the values (slabs) are interchangeable.
00275       Symmetries syms;
00276       syms << ValueSymmetry(IntArgs::create(nslabs,0));
00277 
00278       // For variable order we mimic the custom brancher.  We use
00279       // min-size domain, breaking ties by maximum weight (preferring
00280       // to label larger weights earlier).  To do this, we first sort
00281       // (stably) by maximum weight, then use min-size domain.
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       // No non-assigned orders left
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       // Find order with a) minimum size, b) largest weight
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       // Find first still empty slab (all such slabs are symmetric)
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   // Check number of arguments
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   // Parse options
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       // Read file instance
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   // Compute loss
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   // Set size, if none given
00552   if (_size == 0) {
00553     _size = _norders;
00554   }
00555   // Check size reasonability
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 // Positions in order array
00564 const int order_weight = 0;
00565 const int order_color = 1;
00566 
00567 // CSPLib instance
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 // STATISTICS: example-any