Generated on Thu Mar 22 10:39:31 2012 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  *  Last modified:
00010  *     $Date: 2011-05-11 12:44:17 +0200 (Wed, 11 May 2011) $ by $Author: tack $
00011  *     $Revision: 12001 $
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       }
00340       virtual void archive(Archive& e) const {
00341         Gecode::Choice::archive(e);
00342         e << alternatives() << pos << val;
00343       }
00344     };
00345 
00347     SteelMillBranch(Home home)
00348       : Brancher(home), start(0) {}
00350     SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
00351       : Brancher(home, share, b), start(b.start) {
00352     }
00353 
00354   public:
00356     virtual bool status(const Space& home) const {
00357       const SteelMill& sm = static_cast<const SteelMill&>(home);
00358       for (unsigned int i = start; i < sm.norders; ++i)
00359         if (!sm.slab[i].assigned()) {
00360           start = i;
00361           return true;
00362         }
00363       // No non-assigned orders left
00364       return false;
00365     }
00367     virtual Gecode::Choice* choice(Space& home) {
00368       SteelMill& sm = static_cast<SteelMill&>(home);
00369       assert(!sm.slab[start].assigned());
00370       // Find order with a) minimum size, b) largest weight
00371       unsigned int size = sm.norders;
00372       int weight = 0;
00373       unsigned int pos = start;
00374       for (unsigned int i = start; i<sm.norders; ++i) {
00375         if (!sm.slab[i].assigned()) {
00376           if (sm.slab[i].size() == size && 
00377               sm.orders[i][order_weight] > weight) {
00378             weight = sm.orders[i][order_weight];
00379             pos = i;
00380           } else if (sm.slab[i].size() < size) {
00381             size = sm.slab[i].size();
00382             weight = sm.orders[i][order_weight];
00383             pos = i;
00384           }
00385         }
00386       }
00387       unsigned int val = sm.slab[pos].min();
00388       // Find first still empty slab (all such slabs are symmetric)
00389       unsigned int firstzero = 0;
00390       while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
00391         ++firstzero;
00392       assert(pos < sm.nslabs &&
00393              val < sm.norders);
00394       return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
00395     }
00396     virtual Choice* choice(const Space&, Archive& e) {
00397       unsigned int alt; int pos, val;
00398       e >> alt >> pos >> val;
00399       return new Choice(*this, alt, pos, val);
00400     }
00402     virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00403                               unsigned int a) {
00404       SteelMill& sm = static_cast<SteelMill&>(home);
00405       const Choice& c = static_cast<const Choice&>(_c);
00406       if (a)
00407         return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
00408           ? ES_FAILED : ES_OK;
00409       else
00410         return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
00411           ? ES_FAILED : ES_OK;
00412     }
00414     virtual Actor* copy(Space& home, bool share) {
00415       return new (home) SteelMillBranch(home, share, *this);
00416     }
00418     static void post(Home home) {
00419       (void) new (home) SteelMillBranch(home);
00420     }
00422     virtual size_t dispose(Space&) {
00423       return sizeof(*this);
00424     }
00425   };
00426 };
00427 
00431 int
00432 main(int argc, char* argv[]) {
00433   SteelMillOptions opt("Steel Mill Slab design");
00434   opt.symmetry(SteelMill::SYMMETRY_BRANCHING);
00435   opt.symmetry(SteelMill::SYMMETRY_NONE,"none");
00436   opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
00437   opt.solutions(0);
00438   if (!opt.parse(argc,argv))
00439     return 1;
00440   Script::run<SteelMill,BAB,SteelMillOptions>(opt);
00441   return 0;
00442 }
00443 
00444 
00445 void
00446 SteelMillOptions::help(void) {
00447   Options::help();
00448   std::cerr << "\t(string), optional" << std::endl
00449             << "\t\tBenchmark to load." << std::endl
00450             << "\t\tIf none is given, the standard CSPLib instance is used."
00451             << std::endl;
00452   std::cerr << "\t(unsigned int), optional" << std::endl
00453             << "\t\tNumber of orders to use, in the interval [0..norders]."
00454             << std::endl
00455             << "\t\tIf none is given, all orders are used." << std::endl;
00456 }
00457 
00458 bool
00459 SteelMillOptions::parse(int& argc, char* argv[]) {
00460   Options::parse(argc,argv);
00461   // Check number of arguments
00462   if (argc >= 4) {
00463     std::cerr << "Too many arguments given, max two allowed (given={";
00464     for (int i = 1; i < argc; ++i) {
00465       std::cerr << "\"" << argv[i] << "\"";
00466       if (i < argc-1) std::cerr << ",";
00467     }
00468     std::cerr << "})." << std::endl;
00469     return false;
00470   }
00471   // Parse options
00472   while (argc >= 2) {
00473     bool issize = true;
00474     for (int i = strlen(argv[argc-1]); i-- && issize; )
00475       issize &= (isdigit(argv[argc-1][i]) != 0);
00476     if (issize) {
00477       _size = atoi(argv[argc-1]);
00478     } else {
00479       std::ifstream instance(argv[argc-1]);
00480       if (instance.fail()) {
00481         std::cerr << "Argument \"" << argv[argc-1]
00482                   << "\" is neither an integer nor a readable file"
00483                   << std::endl;
00484         return false;
00485       }
00486       // Read file instance
00487       instance >> _ncapacities;
00488       _capacities = new int[_ncapacities];
00489       _maxcapacity = -1;
00490       for (int i = 0; i < _ncapacities; ++i) {
00491         instance >> _capacities[i];
00492         _maxcapacity = std::max(_maxcapacity, _capacities[i]);
00493       }
00494       instance >> _ncolors >> _norders;
00495       _orders = new int[_norders][2];
00496       for (unsigned int i = 0; i < _norders; ++i) {
00497         instance >> _orders[i][order_weight] >> _orders[i][order_color];
00498       }
00499     }
00500 
00501     --argc;
00502   }
00503   // Compute loss
00504   {
00505     _loss = new int[_maxcapacity+1];
00506     _loss[0] = 0;
00507     int currcap = 0;
00508     for (int c = 1; c < _maxcapacity; ++c) {
00509       if (c > _capacities[currcap]) ++currcap;
00510       _loss[c] = _capacities[currcap] - c;
00511     }
00512   }
00513   // Set size, if none given
00514   if (_size == 0) {
00515     _size = _norders;
00516   }
00517   // Check size reasonability
00518   if (_size == 0 || _size > _norders) {
00519     std::cerr << "Size must be between 1 and " << _norders << std::endl;
00520     return false;
00521   }
00522   return true;
00523 }
00524 
00525 // Positions in order array
00526 const int order_weight = 0;
00527 const int order_color = 1;
00528 
00529 // CSPLib instance
00530 int csplib_capacities[] =
00531   {12, 14, 17, 18, 19,
00532    20, 23, 24, 25, 26,
00533    27, 28, 29, 30, 32,
00534    35, 39, 42, 43, 44};
00535 unsigned int csplib_ncapacities = 20;
00536 unsigned int csplib_maxcapacity = 44;
00537 int csplib_loss[45];
00538 unsigned int csplib_ncolors = 89;
00539 unsigned int csplib_norders = 111;
00540 int csplib_orders[][2] = {
00541   {4, 1},
00542   {22, 2},
00543   {9, 3},
00544   {5, 4},
00545   {8, 5},
00546   {3, 6},
00547   {3, 4},
00548   {4, 7},
00549   {7, 4},
00550   {7, 8},
00551   {3, 6},
00552   {2, 6},
00553   {2, 4},
00554   {8, 9},
00555   {5, 10},
00556   {7, 11},
00557   {4, 7},
00558   {7, 11},
00559   {5, 10},
00560   {7, 11},
00561   {8, 9},
00562   {3, 1},
00563   {25, 12},
00564   {14, 13},
00565   {3, 6},
00566   {22, 14},
00567   {19, 15},
00568   {19, 15},
00569   {22, 16},
00570   {22, 17},
00571   {22, 18},
00572   {20, 19},
00573   {22, 20},
00574   {5, 21},
00575   {4, 22},
00576   {10, 23},
00577   {26, 24},
00578   {17, 25},
00579   {20, 26},
00580   {16, 27},
00581   {10, 28},
00582   {19, 29},
00583   {10, 30},
00584   {10, 31},
00585   {23, 32},
00586   {22, 33},
00587   {26, 34},
00588   {27, 35},
00589   {22, 36},
00590   {27, 37},
00591   {22, 38},
00592   {22, 39},
00593   {13, 40},
00594   {14, 41},
00595   {16, 27},
00596   {26, 34},
00597   {26, 42},
00598   {27, 35},
00599   {22, 36},
00600   {20, 43},
00601   {26, 24},
00602   {22, 44},
00603   {13, 45},
00604   {19, 46},
00605   {20, 47},
00606   {16, 48},
00607   {15, 49},
00608   {17, 50},
00609   {10, 28},
00610   {20, 51},
00611   {5, 52},
00612   {26, 24},
00613   {19, 53},
00614   {15, 54},
00615   {10, 55},
00616   {10, 56},
00617   {13, 57},
00618   {13, 58},
00619   {13, 59},
00620   {12, 60},
00621   {12, 61},
00622   {18, 62},
00623   {10, 63},
00624   {18, 64},
00625   {16, 65},
00626   {20, 66},
00627   {12, 67},
00628   {6, 68},
00629   {6, 68},
00630   {15, 69},
00631   {15, 70},
00632   {15, 70},
00633   {21, 71},
00634   {30, 72},
00635   {30, 73},
00636   {30, 74},
00637   {30, 75},
00638   {23, 76},
00639   {15, 77},
00640   {15, 78},
00641   {27, 79},
00642   {27, 80},
00643   {27, 81},
00644   {27, 82},
00645   {27, 83},
00646   {27, 84},
00647   {27, 79},
00648   {27, 85},
00649   {27, 86},
00650   {10, 87},
00651   {3, 88}
00652 };
00653 
00654 // STATISTICS: example-any