Generated on Wed Nov 5 2014 05:18:16 for Gecode by doxygen 1.7.6.1
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  *  Last modified:
00010  *     $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13820 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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 
00119 class SortByWeight {
00120 public:
00122   order_t orders;
00124   SortByWeight(order_t _orders) : orders(_orders) {}
00126   bool operator() (int i, int j) {
00127     // Order i comes before order j if the weight of i is larger than
00128     // the weight of j.
00129     return (orders[i][order_weight] > orders[j][order_weight]) ||
00130       (orders[i][order_weight] == orders[j][order_weight] && i<j);
00131   }
00132 };
00133 
00162 class SteelMill : public IntMinimizeScript {
00163 protected:
00167   int* capacities;      
00168   int  ncapacities;     
00169   int  maxcapacity;     
00170   int* loss;            
00171   int  ncolors;         
00172   order_t orders;       
00173   unsigned int norders; 
00174   unsigned int nslabs;  
00175 
00176 
00180   IntVarArray slab, 
00181     slabload, 
00182     slabcost; 
00183   IntVar total_cost; 
00184 
00185 
00186 public:
00188   enum {
00189     SYMMETRY_NONE,      
00190     SYMMETRY_BRANCHING, 
00191     SYMMETRY_LDSB       
00192   };
00193 
00195   SteelMill(const SteelMillOptions& opt)
00196     : // Initialize instance data
00197       capacities(opt.capacities()), ncapacities(opt.ncapacities()),
00198       maxcapacity(opt.maxcapacity()), loss(opt.loss()),
00199       ncolors(opt.ncolors()), orders(opt.orders()),
00200       norders(opt.size()), nslabs(opt.size()),
00201       // Initialize problem variables
00202       slab(*this, norders, 0,nslabs-1),
00203       slabload(*this, nslabs, 0,45),
00204       slabcost(*this, nslabs, 0, Int::Limits::max),
00205       total_cost(*this, 0, Int::Limits::max)
00206   {
00207     // Boolean variables for slab[o]==s
00208     BoolVarArgs boolslab(norders*nslabs);
00209     for (unsigned int i = 0; i < norders; ++i) {
00210       BoolVarArgs tmp(nslabs);
00211       for (int j = nslabs; j--; ) {
00212         boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1);
00213       }
00214       channel(*this, tmp, slab[i]);
00215     }
00216 
00217     // Packing constraints
00218     for (unsigned int s = 0; s < nslabs; ++s) {
00219       IntArgs c(norders);
00220       BoolVarArgs x(norders);
00221       for (int i = norders; i--; ) {
00222         c[i] = orders[i][order_weight];
00223         x[i] = boolslab[s + i*nslabs];
00224       }
00225       linear(*this, c, x, IRT_EQ, slabload[s]);
00226     }
00227     // Redundant packing constraint
00228     int totalweight = 0;
00229     for (unsigned int i = norders; i-- ; ) 
00230        totalweight += orders[i][order_weight] ;
00231     linear(*this, slabload, IRT_EQ, totalweight);
00232 
00233 
00234     // Color constraints
00235     IntArgs nofcolor(ncolors);
00236     for (int c = ncolors; c--; ) {
00237       nofcolor[c] = 0;
00238       for (int o = norders; o--; ) {
00239         if (orders[o][order_color] == c) nofcolor[c] += 1;
00240       }
00241     }
00242     BoolVar f(*this, 0, 0);
00243     for (unsigned int s = 0; s < nslabs; ++s) {
00244       BoolVarArgs hascolor(ncolors);
00245       for (int c = ncolors; c--; ) {
00246         if (nofcolor[c]) {
00247           BoolVarArgs hasc(nofcolor[c]);
00248           int pos = 0;
00249           for (int o = norders; o--; ) {
00250             if (orders[o][order_color] == c)
00251               hasc[pos++] = boolslab[s + o*nslabs];
00252           }
00253           assert(pos == nofcolor[c]);
00254           hascolor[c] = BoolVar(*this, 0, 1);
00255           rel(*this, BOT_OR, hasc, hascolor[c]);
00256         } else {
00257           hascolor[c] = f;
00258         }
00259       }
00260       linear(*this, hascolor, IRT_LQ, 2);
00261     }
00262 
00263     // Compute slabcost
00264     IntArgs l(maxcapacity, loss);
00265     for (int s = nslabs; s--; ) {
00266       element(*this, l, slabload[s], slabcost[s]);
00267     }
00268     linear(*this, slabcost, IRT_EQ, total_cost);
00269 
00270     // Add branching
00271     if (opt.symmetry() == SYMMETRY_BRANCHING) {
00272       // Symmetry breaking branching
00273       SteelMillBranch::post(*this);
00274     } else if (opt.symmetry() == SYMMETRY_NONE) {
00275       branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN());
00276     } else { // opt.symmetry() == SYMMETRY_LDSB
00277       // There is one symmetry: the values (slabs) are interchangeable.
00278       Symmetries syms;
00279       syms << ValueSymmetry(IntArgs::create(nslabs,0));
00280 
00281       // For variable order we mimic the custom brancher.  We use
00282       // min-size domain, breaking ties by maximum weight (preferring
00283       // to label larger weights earlier).  To do this, we first sort
00284       // (stably) by maximum weight, then use min-size domain.
00285       SortByWeight sbw(orders);
00286       IntArgs indices(norders);
00287       for (unsigned int i = 0 ; i < norders ; i++)
00288         indices[i] = i;
00289       Support::quicksort(&indices[0],norders,sbw);
00290       IntVarArgs sorted_orders(norders);
00291       for (unsigned int i = 0 ; i < norders ; i++) {
00292         sorted_orders[i] = slab[indices[i]];
00293       }
00294       branch(*this, sorted_orders, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
00295     }
00296   }
00297 
00299   virtual void
00300   print(std::ostream& os) const {
00301     os << "What slab="  << slab << std::endl;
00302     os << "Slab load="  << slabload << std::endl;
00303     os << "Slab cost="  << slabcost << std::endl;
00304     os << "Total cost=" << total_cost << std::endl;
00305     int nslabsused = 0;
00306     int nslabscost = 0;
00307     bool unassigned = false;
00308     for (int i = nslabs; i--; ) {
00309       if (!slabload[i].assigned() || !slabcost[i].assigned()) {
00310         unassigned = true;
00311         break;
00312       }
00313       if (slabload[i].min()>0) ++nslabsused;
00314       if (slabcost[i].min()>0) ++nslabscost;
00315     }
00316     if (!unassigned)
00317       os << "Number of slabs used=" << nslabsused
00318          << ", slabs with cost="    << nslabscost
00319          << std::endl;
00320     os << std::endl;
00321   }
00322 
00324   SteelMill(bool share, SteelMill& s)
00325     : IntMinimizeScript(share,s),
00326       capacities(s.capacities), ncapacities(s.ncapacities),
00327       maxcapacity(s.maxcapacity), loss(s.loss),
00328       ncolors(s.ncolors), orders(s.orders),
00329       norders(s.norders), nslabs(s.nslabs) {
00330     slab.update(*this, share, s.slab);
00331     slabload.update(*this, share, s.slabload);
00332     slabcost.update(*this, share, s.slabcost);
00333     total_cost.update(*this, share, s.total_cost);
00334   }
00336   virtual Space*
00337   copy(bool share) {
00338     return new SteelMill(share,*this);
00339   }
00341   virtual IntVar cost(void) const {
00342     return total_cost;
00343   }
00344 
00345 
00354   class SteelMillBranch : Brancher {
00355   protected:
00357     mutable int start;
00359     class Choice : public Gecode::Choice {
00360     public:
00362       int pos;
00364       int val;
00368       Choice(const Brancher& b, unsigned int a, int pos0, int val0)
00369         : Gecode::Choice(b,a), pos(pos0), val(val0) {}
00371       virtual size_t size(void) const {
00372         return sizeof(Choice);
00373       }
00375       virtual void archive(Archive& e) const {
00376         Gecode::Choice::archive(e);
00377         e << alternatives() << pos << val;
00378       }
00379     };
00380 
00382     SteelMillBranch(Home home)
00383       : Brancher(home), start(0) {}
00385     SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
00386       : Brancher(home, share, b), start(b.start) {
00387     }
00388 
00389   public:
00391     virtual bool status(const Space& home) const {
00392       const SteelMill& sm = static_cast<const SteelMill&>(home);
00393       for (unsigned int i = start; i < sm.norders; ++i)
00394         if (!sm.slab[i].assigned()) {
00395           start = i;
00396           return true;
00397         }
00398       // No non-assigned orders left
00399       return false;
00400     }
00402     virtual Gecode::Choice* choice(Space& home) {
00403       SteelMill& sm = static_cast<SteelMill&>(home);
00404       assert(!sm.slab[start].assigned());
00405       // Find order with a) minimum size, b) largest weight
00406       unsigned int size = sm.norders;
00407       int weight = 0;
00408       unsigned int pos = start;
00409       for (unsigned int i = start; i<sm.norders; ++i) {
00410         if (!sm.slab[i].assigned()) {
00411           if (sm.slab[i].size() == size && 
00412               sm.orders[i][order_weight] > weight) {
00413             weight = sm.orders[i][order_weight];
00414             pos = i;
00415           } else if (sm.slab[i].size() < size) {
00416             size = sm.slab[i].size();
00417             weight = sm.orders[i][order_weight];
00418             pos = i;
00419           }
00420         }
00421       }
00422       unsigned int val = sm.slab[pos].min();
00423       // Find first still empty slab (all such slabs are symmetric)
00424       unsigned int firstzero = 0;
00425       while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
00426         ++firstzero;
00427       assert(pos < sm.nslabs &&
00428              val < sm.norders);
00429       return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
00430     }
00431     virtual Choice* choice(const Space&, Archive& e) {
00432       unsigned int alt; int pos, val;
00433       e >> alt >> pos >> val;
00434       return new Choice(*this, alt, pos, val);
00435     }
00437     virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00438                               unsigned int a) {
00439       SteelMill& sm = static_cast<SteelMill&>(home);
00440       const Choice& c = static_cast<const Choice&>(_c);
00441       if (a)
00442         return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
00443           ? ES_FAILED : ES_OK;
00444       else
00445         return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
00446           ? ES_FAILED : ES_OK;
00447     }
00449     virtual void print(const Space&, const Gecode::Choice& _c, 
00450                        unsigned int a,
00451                        std::ostream& o) const {
00452       const Choice& c = static_cast<const Choice&>(_c);
00453       o << "slab[" << c.pos << "] "
00454         << ((a == 0) ? "=" : "!=")
00455         << " " << c.val;
00456     }
00458     virtual Actor* copy(Space& home, bool share) {
00459       return new (home) SteelMillBranch(home, share, *this);
00460     }
00462     static BrancherHandle post(Home home) {
00463       return *new (home) SteelMillBranch(home);
00464     }
00466     virtual size_t dispose(Space&) {
00467       return sizeof(*this);
00468     }
00469   };
00470 };
00471 
00475 int
00476 main(int argc, char* argv[]) {
00477   SteelMillOptions opt("Steel Mill Slab design");
00478   opt.symmetry(SteelMill::SYMMETRY_BRANCHING);
00479   opt.symmetry(SteelMill::SYMMETRY_NONE,"none");
00480   opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
00481   opt.symmetry(SteelMill::SYMMETRY_LDSB,"ldsb");
00482   opt.solutions(0);
00483   if (!opt.parse(argc,argv))
00484     return 1;
00485   Script::run<SteelMill,BAB,SteelMillOptions>(opt);
00486   return 0;
00487 }
00488 
00489 
00490 void
00491 SteelMillOptions::help(void) {
00492   Options::help();
00493   std::cerr << "\t(string), optional" << std::endl
00494             << "\t\tBenchmark to load." << std::endl
00495             << "\t\tIf none is given, the standard CSPLib instance is used."
00496             << std::endl;
00497   std::cerr << "\t(unsigned int), optional" << std::endl
00498             << "\t\tNumber of orders to use, in the interval [0..norders]."
00499             << std::endl
00500             << "\t\tIf none is given, all orders are used." << std::endl;
00501 }
00502 
00503 bool
00504 SteelMillOptions::parse(int& argc, char* argv[]) {
00505   Options::parse(argc,argv);
00506   // Check number of arguments
00507   if (argc >= 4) {
00508     std::cerr << "Too many arguments given, max two allowed (given={";
00509     for (int i = 1; i < argc; ++i) {
00510       std::cerr << "\"" << argv[i] << "\"";
00511       if (i < argc-1) std::cerr << ",";
00512     }
00513     std::cerr << "})." << std::endl;
00514     return false;
00515   }
00516   // Parse options
00517   while (argc >= 2) {
00518     bool issize = true;
00519     for (int i = strlen(argv[argc-1]); i-- && issize; )
00520       issize &= (isdigit(argv[argc-1][i]) != 0);
00521     if (issize) {
00522       _size = atoi(argv[argc-1]);
00523     } else {
00524       std::ifstream instance(argv[argc-1]);
00525       if (instance.fail()) {
00526         std::cerr << "Argument \"" << argv[argc-1]
00527                   << "\" is neither an integer nor a readable file"
00528                   << std::endl;
00529         return false;
00530       }
00531       // Read file instance
00532       instance >> _ncapacities;
00533       _capacities = new int[_ncapacities];
00534       _maxcapacity = -1;
00535       for (int i = 0; i < _ncapacities; ++i) {
00536         instance >> _capacities[i];
00537         _maxcapacity = std::max(_maxcapacity, _capacities[i]);
00538       }
00539       instance >> _ncolors >> _norders;
00540       _orders = new int[_norders][2];
00541       for (unsigned int i = 0; i < _norders; ++i) {
00542         instance >> _orders[i][order_weight] >> _orders[i][order_color];
00543       }
00544     }
00545 
00546     --argc;
00547   }
00548   // Compute loss
00549   {
00550     _loss = new int[_maxcapacity+1];
00551     _loss[0] = 0;
00552     int currcap = 0;
00553     for (int c = 1; c < _maxcapacity; ++c) {
00554       if (c > _capacities[currcap]) ++currcap;
00555       _loss[c] = _capacities[currcap] - c;
00556     }
00557   }
00558   // Set size, if none given
00559   if (_size == 0) {
00560     _size = _norders;
00561   }
00562   // Check size reasonability
00563   if (_size == 0 || _size > _norders) {
00564     std::cerr << "Size must be between 1 and " << _norders << std::endl;
00565     return false;
00566   }
00567   return true;
00568 }
00569 
00570 // Positions in order array
00571 const int order_weight = 0;
00572 const int order_color = 1;
00573 
00574 // CSPLib instance
00575 int csplib_capacities[] =
00576   {12, 14, 17, 18, 19,
00577    20, 23, 24, 25, 26,
00578    27, 28, 29, 30, 32,
00579    35, 39, 42, 43, 44};
00580 unsigned int csplib_ncapacities = 20;
00581 unsigned int csplib_maxcapacity = 44;
00582 int csplib_loss[45];
00583 unsigned int csplib_ncolors = 89;
00584 unsigned int csplib_norders = 111;
00585 int csplib_orders[][2] = {
00586   {4, 1},
00587   {22, 2},
00588   {9, 3},
00589   {5, 4},
00590   {8, 5},
00591   {3, 6},
00592   {3, 4},
00593   {4, 7},
00594   {7, 4},
00595   {7, 8},
00596   {3, 6},
00597   {2, 6},
00598   {2, 4},
00599   {8, 9},
00600   {5, 10},
00601   {7, 11},
00602   {4, 7},
00603   {7, 11},
00604   {5, 10},
00605   {7, 11},
00606   {8, 9},
00607   {3, 1},
00608   {25, 12},
00609   {14, 13},
00610   {3, 6},
00611   {22, 14},
00612   {19, 15},
00613   {19, 15},
00614   {22, 16},
00615   {22, 17},
00616   {22, 18},
00617   {20, 19},
00618   {22, 20},
00619   {5, 21},
00620   {4, 22},
00621   {10, 23},
00622   {26, 24},
00623   {17, 25},
00624   {20, 26},
00625   {16, 27},
00626   {10, 28},
00627   {19, 29},
00628   {10, 30},
00629   {10, 31},
00630   {23, 32},
00631   {22, 33},
00632   {26, 34},
00633   {27, 35},
00634   {22, 36},
00635   {27, 37},
00636   {22, 38},
00637   {22, 39},
00638   {13, 40},
00639   {14, 41},
00640   {16, 27},
00641   {26, 34},
00642   {26, 42},
00643   {27, 35},
00644   {22, 36},
00645   {20, 43},
00646   {26, 24},
00647   {22, 44},
00648   {13, 45},
00649   {19, 46},
00650   {20, 47},
00651   {16, 48},
00652   {15, 49},
00653   {17, 50},
00654   {10, 28},
00655   {20, 51},
00656   {5, 52},
00657   {26, 24},
00658   {19, 53},
00659   {15, 54},
00660   {10, 55},
00661   {10, 56},
00662   {13, 57},
00663   {13, 58},
00664   {13, 59},
00665   {12, 60},
00666   {12, 61},
00667   {18, 62},
00668   {10, 63},
00669   {18, 64},
00670   {16, 65},
00671   {20, 66},
00672   {12, 67},
00673   {6, 68},
00674   {6, 68},
00675   {15, 69},
00676   {15, 70},
00677   {15, 70},
00678   {21, 71},
00679   {30, 72},
00680   {30, 73},
00681   {30, 74},
00682   {30, 75},
00683   {23, 76},
00684   {15, 77},
00685   {15, 78},
00686   {27, 79},
00687   {27, 80},
00688   {27, 81},
00689   {27, 82},
00690   {27, 83},
00691   {27, 84},
00692   {27, 79},
00693   {27, 85},
00694   {27, 86},
00695   {10, 87},
00696   {3, 88}
00697 };
00698 
00699 // STATISTICS: example-any