Generated on Fri May 13 2011 22:41:13 for Gecode by doxygen 1.7.1

car-sequencing.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, 2009
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $
00011  *     $Revision: 11473 $
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 <iomanip>
00043 
00044 using namespace Gecode;
00045 
00046 // Problems
00047 namespace {
00048   // Problem data
00049   extern const int* problems[];
00050   // Number of problems
00051   extern const unsigned int n_problems;
00052 }
00053 
00054 namespace {
00060   class CarOptions : public SizeOptions {
00061   private:
00063     Driver::UnsignedIntOption _maxstall;
00064 
00065   public:
00067     CarOptions(const char* s)
00068       : SizeOptions(s),
00069         _maxstall("-maxstall", "Maximum numbere of stalls", 30)
00070     {
00071       // Add options
00072       add(_maxstall);
00073     }
00075     void parse(int& argc, char* argv[]) {
00076       SizeOptions::parse(argc,argv);
00077     }
00079     int maxstall(void) const { return _maxstall.value(); }
00080   };
00081 
00082 
00100   template <class View>
00101   class PushToEnd : public NaryOnePropagator<View,Int::PC_INT_BND> {
00102   protected:
00103     using NaryOnePropagator<View,Int::PC_INT_BND>::x;
00104     using NaryOnePropagator<View,Int::PC_INT_BND>::y;
00105     int val;
00106 
00108     PushToEnd(Space& home, bool share, PushToEnd& p);
00110     PushToEnd(Space& home, ViewArray<View>& x0, View y0, int val0);
00111   public:
00113     PushToEnd(Space& home, bool share, Propagator& p, 
00114               ViewArray<View>& x0, View y0, int val0);
00116     virtual Actor* copy(Space& home, bool share);
00118     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00120     static  ExecStatus post(Space& home, 
00121                             ViewArray<View>& x0, View y0, int val0);
00122   };
00123 
00124   template <class View>
00125   inline
00126   PushToEnd<View>::PushToEnd(Space& home, 
00127                              ViewArray<View>& x0, View y0, int val0)
00128     : NaryOnePropagator<View,Int::PC_INT_BND>(home,x0,y0), val(val0) {}
00129 
00130   template <class View>
00131   ExecStatus
00132   PushToEnd<View>::post(Space& home, 
00133                         ViewArray<View>& x0, View y0, int val0) {
00134     (void) new (home) PushToEnd<View>(home,x0,y0,val0);
00135     return ES_OK;
00136   }
00137 
00138   template <class View>
00139   inline
00140   PushToEnd<View>::PushToEnd(Space& home, bool share, PushToEnd<View>& p)
00141     : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p), val(p.val) {}
00142 
00143   template <class View>
00144   inline
00145   PushToEnd<View>::PushToEnd(Space& home, bool share, Propagator& p,
00146                              ViewArray<View>& x0, View y0, int val0)
00147   : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p,x0,y0), val(val0) {}
00148 
00149   template <class View>
00150   Actor*
00151   PushToEnd<View>::copy(Space& home, bool share) {
00152     return new (home) PushToEnd<View>(home,share,*this);
00153   }
00154 
00155   template <class View>
00156   ExecStatus
00157   PushToEnd<View>::propagate(Space& home, const ModEventDelta&) {
00158     // Find number of required positions
00159     int min = 0;
00160     for (int i = x.size(); i-- && x[i].min() >= val-1; ) {
00161       ++min;
00162     }
00163     // Find number of possible positions
00164     int max = 0;
00165     int i = x.size();
00166     while (i--) {
00167       if (x[i].max() != val) break;
00168       ++max;
00169       if (max >= y.max()) break;
00170     }
00171     // No variables later than max can have value val
00172     while (i--) {
00173       GECODE_ME_CHECK(x[i].le(home, val));
00174     }
00175     
00176     // Constrain y to be in {min..max}
00177     GECODE_ME_CHECK(y.gq(home, min));
00178     GECODE_ME_CHECK(y.lq(home, max));
00179 
00180     // At least the y.min() last values have value val
00181     for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
00182       GECODE_ME_CHECK(x[pos].eq(home, val));
00183     }
00184     
00185     return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00186   }
00187 
00190   void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
00191     ViewArray<Int::IntView> vx(home, x);
00192     Int::IntView vy(y);
00193     GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
00194   }
00195 
00196 }
00197 
00198 
00210 class CarSequencing : public Script {
00211 public:
00213   enum {
00214     SEARCH_BAB,    
00215     SEARCH_RESTART 
00216   };
00218   enum {
00219     BRANCH_INORDER,  
00220     BRANCH_MIDDLE  
00221   };
00223   enum {
00224     PROP_REGULAR,  
00225     PROP_CUSTOM    
00226   };
00227 protected:
00229   const int problem;
00231   const int ncars;
00233   const int noptions; 
00235   const int nclasses;
00237   const int maxstall;
00239   const int stallval;
00241   const int endval;
00243   IntVar nstall;
00245   IntVar nend;
00247   IntVarArray s;
00248 public:
00250   CarSequencing(const CarOptions& opt)
00251     : problem(opt.size()),
00252       ncars(problems[problem][0]), 
00253       noptions(problems[problem][1]), 
00254       nclasses(problems[problem][2]),
00255       maxstall(opt.maxstall()),
00256       stallval(nclasses),
00257       endval(nclasses+1),
00258       nstall(*this, 0, maxstall),
00259       nend(*this, 0, maxstall),
00260       s(*this, ncars+maxstall, 0, nclasses+1)
00261   {
00262     // Read problem
00263     const int* probit = problems[problem] + 3;
00264 
00265     // Sequence requirements for the options.
00266     IntArgs max(noptions), block(noptions);
00267     for (int i = 0; i < noptions; ++i ) {
00268       max[i] = *probit++;
00269     }
00270     for (int i = 0; i < noptions; ++i ) {
00271       block[i] = *probit++;
00272     }
00273     // Number of cars per class
00274     IntArgs ncc(nclasses);
00275     // What classes require an option
00276     IntSetArgs classes(noptions);
00277     int** cdata = new int*[noptions]; 
00278     for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00279     int* n = new int[noptions];
00280     for (int i = noptions; i--; ) n[i] = 0;
00281     // Read data
00282     for (int c = 0; c < nclasses; ++c) {
00283       *probit++;
00284       ncc[c] = *probit++;
00285       for (int o = 0; o < noptions; ++o) {
00286         if (*probit++) {
00287           cdata[o][n[o]++] = c;
00288         }
00289       }
00290     }
00291     // Transfer specification data to int-sets
00292     for (int o = noptions; o--; ) {
00293       classes[o] = IntSet(cdata[o], n[o]);
00294       delete [] cdata[o];
00295     }
00296     delete [] cdata;
00297     delete [] n;
00298 
00299     // Count the cars
00300     IntSetArgs c(nclasses+2);
00301     for (int i = nclasses; i--; ) {
00302       c[i] = IntSet(ncc[i], ncc[i]);
00303     }
00304     c[stallval] = IntSet(0, maxstall);
00305     c[  endval] = IntSet(0, maxstall);
00306     count(*this, s, c);
00307 
00308     // Count number of end and stallss
00309     count(*this, s, stallval, IRT_EQ, nstall);
00310     count(*this, s,   endval, IRT_EQ,   nend);
00311     rel(*this, nstall+nend == maxstall);
00312 
00313     // Make sure nothing is overloaded
00314     IntSet one(1, 1);
00315     for (int o = noptions; o--; ) {
00316       // sb[i] reflects if car s[i] has option o
00317       BoolVarArgs sb(s.size());
00318       for (int i = s.size(); i--; ) {
00319         BoolVar b(*this, 0, 1);
00320         dom(*this, s[i], classes[o], b);
00321         sb[i] = b;
00322       }
00323       sequence(*this, sb, one, block[o], 0, max[o]);
00324     }
00325 
00326     // End-markers located at end only
00327     switch (opt.propagation()) {
00328     case PROP_REGULAR: {
00329       IntArgs notend(nclasses), notstallend(nclasses+1);
00330       for (int i = nclasses; i--; ) {
00331         notend[i] = i;
00332         notstallend[i] = i;
00333       }
00334       notstallend[nclasses] = stallval;
00335       REG r = *REG(notend) + REG(notstallend) + *REG(endval);
00336       extensional(*this, s, r);
00337       for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
00338         rel(*this, (nend > i) >> (s[pos]==endval));
00339       }
00340     } break;
00341     case PROP_CUSTOM: {
00342       pushtoend(*this, s, nend, endval);
00343     } break;
00344     }
00345     
00346 
00347     // Branching
00348     switch (opt.branching()) {
00349     case BRANCH_INORDER:
00350       branch(*this, s, INT_VAR_NONE, INT_VAL_MIN);
00351       break;
00352     case BRANCH_MIDDLE: {
00353       IntVarArgs m(s.size());
00354       int mid = s.size() / 2;
00355       int pos = 0;
00356       m[pos++] = s[mid];
00357       for (int i = 1; i <= m.size()/2; ++i) {
00358         if (mid-i >= 0)
00359           m[pos++] = s[mid-i];
00360         if (mid+i < s.size())
00361           m[pos++] = s[mid+i];
00362       }
00363       assert(pos == m.size());
00364       branch(*this, m, INT_VAR_NONE, INT_VAL_MIN);
00365       break;
00366     }
00367     }
00368   }
00369         
00371   virtual void constrain(const Space& _best) {
00372     const CarSequencing& best = static_cast<const CarSequencing&>(_best);
00373     rel(*this, nstall, IRT_LE, best.nstall.val());
00374   }
00375 
00377   virtual void
00378   print(std::ostream& os) const {
00379     int width = nclasses > 9 ? 2 : 1;
00380     const char* space = nclasses > 9 ? " " : "";
00381     os << "Stall slots=" << nstall 
00382        << ", End slots=" << nend << std::endl;
00383     int i = 0;
00384     for (; i < s.size(); ++i) {
00385       if (s[i].assigned()) {
00386         int v = s[i].val();
00387         if (v == endval) break;
00388         if (v == stallval) os << space << "_ ";
00389         else               os << std::setw(width) << v << " ";
00390       } else {
00391         os << space << "? ";    
00392       }
00393       if ((i+1)%20 == 0) os << std::endl;
00394     }
00395     if (i%20)
00396       os << std::endl;
00397     os << std::endl;
00398   }
00399 
00401   CarSequencing(bool share, CarSequencing& cs)
00402     : Script(share,cs), 
00403       problem(cs.problem),
00404       ncars(cs.ncars),
00405       noptions(cs.noptions),
00406       nclasses(cs.nclasses),
00407       maxstall(cs.maxstall),
00408       stallval(cs.stallval),
00409       endval(cs.endval)
00410   {
00411     nstall.update(*this, share, cs.nstall);
00412     nend.update(*this, share, cs.nend);
00413     s.update(*this, share, cs.s);
00414   }
00416   virtual Space*
00417   copy(bool share) {
00418     return new CarSequencing(share,*this);
00419   }
00420 };
00421 
00425 int
00426 main(int argc, char* argv[]) {
00427   CarOptions opt("CarSequencing");
00428   opt.solutions(0);
00429   opt.size(0);
00430   opt.search(CarSequencing::SEARCH_BAB);
00431   opt.search(CarSequencing::SEARCH_BAB, "bab");
00432   opt.search(CarSequencing::SEARCH_RESTART, "restart");
00433   opt.branching(CarSequencing::BRANCH_INORDER);
00434   opt.branching(CarSequencing::BRANCH_INORDER,  "inorder");
00435   opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00436   opt.propagation(CarSequencing::PROP_CUSTOM);
00437   opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00438   opt.propagation(CarSequencing::PROP_CUSTOM,  "custom");
00439   opt.parse(argc,argv);
00440   if (opt.size() >= n_problems) {
00441     std::cerr << "Error: size must be between 0 and "
00442               << n_problems-1 << std::endl;
00443     return 1;
00444   }
00445 
00446   switch (opt.search()) {
00447   case CarSequencing::SEARCH_BAB:
00448     Script::run<CarSequencing,BAB,CarOptions>(opt); break;
00449   case CarSequencing::SEARCH_RESTART:
00450     Script::run<CarSequencing,Restart,CarOptions>(opt); break;
00451   }
00452   return 0;
00453 }
00454 
00455 
00456 namespace {
00458 
00460   const int p0[] = {
00461     10, 5, 6,
00462     1, 2, 1, 2, 1,
00463     2, 3, 3, 5, 5,
00464     0, 1, 1, 0, 1, 1, 0, 
00465     1, 1, 0, 0, 0, 1, 0, 
00466     2, 2, 0, 1, 0, 0, 1, 
00467     3, 2, 0, 1, 0, 1, 0, 
00468     4, 2, 1, 0, 1, 0, 0, 
00469     5, 2, 1, 1, 0, 0, 0
00470   };
00471 
00472   // ---------------------------------
00473   //  Problem 4/72  (Regin & Puget   // 1)
00474   // ---------------------------------
00475   const int p1[] = {
00476     100, 5, 22,
00477     1, 2, 1, 2, 1,
00478     2, 3, 3, 5, 5,
00479     0, 6, 1, 0, 0, 1, 0, 
00480     1, 10, 1, 1, 1, 0, 0, 
00481     2, 2, 1, 1, 0, 0, 1, 
00482     3, 2, 0, 1, 1, 0, 0, 
00483     4, 8, 0, 0, 0, 1, 0, 
00484     5, 15, 0, 1, 0, 0, 0, 
00485     6, 1, 0, 1, 1, 1, 0, 
00486     7, 5, 0, 0, 1, 1, 0, 
00487     8, 2, 1, 0, 1, 1, 0, 
00488     9, 3, 0, 0, 1, 0, 0, 
00489     10, 2, 1, 0, 1, 0, 0, 
00490     11, 1, 1, 1, 1, 0, 1, 
00491     12, 8, 0, 1, 0, 1, 0, 
00492     13, 3, 1, 0, 0, 1, 1, 
00493     14, 10, 1, 0, 0, 0, 0, 
00494     15, 4, 0, 1, 0, 0, 1, 
00495     16, 4, 0, 0, 0, 0, 1, 
00496     17, 2, 1, 0, 0, 0, 1, 
00497     18, 4, 1, 1, 0, 0, 0, 
00498     19, 6, 1, 1, 0, 1, 0, 
00499     20, 1, 1, 0, 1, 0, 1, 
00500     21, 1, 1, 1, 1, 1, 1, 
00501   };
00502 
00503   // --------------------------------
00504   //  Problem 6/76, (Regin & Puget   // 2)
00505   // --------------------------------
00506   const int p2[] = {
00507     100, 5, 22,
00508     1, 2, 1, 2, 1,
00509     2, 3, 3, 5, 5,
00510     0, 13, 1, 0, 0, 0, 0, 
00511     1, 8, 0, 0, 0, 1, 0, 
00512     2, 7, 0, 1, 0, 0, 0, 
00513     3, 1, 1, 0, 0, 1, 0, 
00514     4, 12, 0, 0, 1, 0, 0, 
00515     5, 5, 0, 1, 0, 1, 0, 
00516     6, 5, 0, 0, 1, 1, 0, 
00517     7, 6, 0, 1, 1, 0, 0, 
00518     8, 3, 1, 0, 0, 0, 1, 
00519     9, 12, 1, 1, 0, 0, 0, 
00520     10, 8, 1, 1, 0, 1, 0, 
00521     11, 2, 1, 0, 0, 1, 1, 
00522     12, 2, 1, 1, 1, 0, 0, 
00523     13, 1, 0, 1, 0, 1, 1, 
00524     14, 4, 1, 0, 1, 0, 0, 
00525     15, 4, 0, 1, 0, 0, 1, 
00526     16, 1, 1, 1, 0, 1, 1, 
00527     17, 2, 1, 0, 1, 1, 0, 
00528     18, 1, 0, 0, 0, 0, 1, 
00529     19, 1, 1, 1, 1, 1, 0, 
00530     20, 1, 1, 1, 0, 0, 1, 
00531     21, 1, 0, 1, 1, 1, 0, 
00532   };
00533 
00534   // ---------------------------------
00535   //  Problem 10/93, (Regin & Puget   // 3)
00536   // ---------------------------------
00537   const int p3[] = {
00538     100, 5, 25,
00539     1, 2, 1, 2, 1,
00540     2, 3, 3, 5, 5,
00541     0, 7, 1, 0, 0, 1, 0,
00542     1, 11, 1, 1, 0, 0, 0,
00543     2, 1, 0, 1, 1, 1, 1,
00544     3, 3, 1, 0, 1, 0, 0,
00545     4, 15, 0, 1, 0, 0, 0,
00546     5, 2, 1, 0, 1, 1, 0,
00547     6, 8, 0, 1, 0, 1, 0,
00548     7, 5, 0, 0, 1, 0, 0,
00549     8, 3, 0, 0, 0, 1, 0,
00550     9, 4, 0, 1, 1, 1, 0,
00551     10, 5, 1, 0, 0, 0, 0,
00552     11, 2, 1, 1, 1, 0, 1,
00553     12, 6, 0, 1, 1, 0, 0,
00554     13, 2, 0, 0, 1, 0, 1,
00555     14, 2, 0, 1, 0, 0, 1,
00556     15, 4, 1, 1, 1, 1, 0,
00557     16, 3, 1, 0, 0, 0, 1,
00558     17, 5, 1, 1, 0, 1, 0,
00559     18, 2, 1, 1, 1, 0, 0,
00560     19, 4, 1, 1, 0, 0, 1,
00561     20, 1, 1, 0, 0, 1, 1,
00562     21, 1, 1, 1, 0, 1, 1,
00563     22, 1, 0, 1, 0, 1, 1,
00564     23, 1, 0, 1, 1, 0, 1,
00565     24, 2, 0, 0, 0, 0, 1,
00566   };
00567 
00568   // --------------
00569   //  Problem 16/81,
00570   // --------------
00571   const int p4[] = {
00572     100, 5, 26,
00573     1, 2, 1, 2, 1,
00574     2, 3, 3, 5, 5,
00575     0, 10, 1, 0, 0, 0, 0,
00576     1, 2, 0, 0, 0, 0, 1,
00577     2, 8, 0, 1, 0, 1, 0,
00578     3, 8, 0, 0, 0, 1, 0,
00579     4, 6, 0, 1, 1, 0, 0,
00580     5, 11, 0, 1, 0, 0, 0,
00581     6, 3, 0, 0, 1, 0, 0,
00582     7, 2, 0, 0, 1, 1, 0,
00583     8, 7, 1, 1, 0, 0, 0,
00584     9, 2, 1, 0, 0, 1, 1,
00585     10, 4, 1, 0, 1, 0, 0,
00586     11, 7, 1, 0, 0, 1, 0,
00587     12, 1, 1, 1, 1, 0, 1,
00588     13, 3, 0, 1, 1, 1, 0,
00589     14, 4, 0, 1, 0, 0, 1,
00590     15, 5, 1, 1, 1, 0, 0,
00591     16, 2, 1, 1, 0, 0, 1,
00592     17, 1, 1, 0, 1, 1, 1,
00593     18, 2, 1, 0, 1, 1, 0,
00594     19, 3, 1, 0, 0, 0, 1,
00595     20, 2, 0, 1, 1, 0, 1,
00596     21, 1, 0, 1, 0, 1, 1,
00597     22, 3, 1, 1, 0, 1, 0,
00598     23, 1, 0, 0, 1, 1, 1,
00599     24, 1, 1, 1, 1, 1, 1,
00600     25, 1, 1, 1, 1, 1, 0,
00601   };
00602 
00603   // ----------------------------------
00604   //  Problem 19/71,  (Regin & Puget   // 4)
00605   // ----------------------------------
00606   const int p5[] = {
00607     100, 5, 23,
00608     1, 2, 1, 2, 1,
00609     2, 3, 3, 5, 5,
00610     0, 2, 0, 0, 0, 1, 1,
00611     1, 2, 0, 0, 1, 0, 1,
00612     2, 5, 0, 1, 1, 1, 0,
00613     3, 4, 0, 0, 0, 1, 0,
00614     4, 4, 0, 1, 0, 1, 0,
00615     5, 1, 1, 1, 0, 0, 1,
00616     6, 3, 1, 1, 1, 0, 1,
00617     7, 4, 0, 0, 1, 0, 0,
00618     8, 19, 0, 1, 0, 0, 0,
00619     9, 7, 1, 1, 0, 1, 0,
00620     10, 10, 1, 0, 0, 0, 0,
00621     11, 1, 0, 0, 1, 1, 0,
00622     12, 5, 1, 1, 1, 1, 0,
00623     13, 2, 1, 0, 1, 1, 0,
00624     14, 6, 1, 1, 0, 0, 0,
00625     15, 4, 1, 1, 1, 0, 0,
00626     16, 8, 1, 0, 0, 1, 0,
00627     17, 1, 1, 0, 0, 0, 1,
00628     18, 4, 0, 1, 1, 0, 0,
00629     19, 2, 0, 0, 0, 0, 1,
00630     20, 4, 0, 1, 0, 0, 1,
00631     21, 1, 1, 1, 0, 1, 1,
00632     22, 1, 0, 1, 1, 0, 1,
00633   };
00634 
00635   const int* problems[] = {
00636     &p0[0],
00637     &p1[0],
00638     &p2[0],
00639     &p3[0],
00640     &p4[0],
00641     &p5[0],
00642   };
00643 
00645   const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00646 };
00647 
00648 // STATISTICS: example-any
00649