Generated on Tue Jul 27 2010 21:59:09 for Gecode by doxygen 1.7.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: 2010-05-07 10:33:59 +0200 (Fri, 07 May 2010) $ by $Author: zayenz $
00011  *     $Revision: 10884 $
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 
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     : // Initialize instance data
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       // Initialize problem variables
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     // Boolean variables for slab[o]==s
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     // Packing constraints
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     // Redundant packing constraint
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     // Color constraints
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     // Compute slabcost
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     // Add branching
00255     if (opt.symmetry() == SYMMETRY_BRANCHING) {
00256       // Symmetry breaking branching
00257       SteelMillBranch::post(*this);
00258     } else { // opt.symmetry() == SYMMETRY_NONE
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(Home 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       // No non-assigned orders left
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       // Find order with a) minimum size, b) largest weight
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       // Find first still empty slab (all such slabs are symmetric)
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(Home home) {
00409       (void) new (home) SteelMillBranch(home);
00410     }
00412     virtual size_t dispose(Space&) {
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   // Check number of arguments
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   // Parse options
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       // Read file instance
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   // Compute loss
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   // Set size, if none given
00504   if (_size == 0) {
00505     _size = _norders;
00506   }
00507   // Check size reasonability
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 // Positions in order array
00516 const int order_weight = 0;
00517 const int order_color = 1;
00518 
00519 // CSPLib instance
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 // STATISTICS: example-any