Generated on Wed Nov 5 2014 05:18:15 for Gecode by doxygen 1.7.6.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: 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 <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     {
00166       int i = x.size();
00167       while (i--) {
00168         if (x[i].max() != val) break;
00169         ++max;
00170         if (max >= y.max()) break;
00171       }
00172       // No variables later than max can have value val
00173       while (i--) {
00174         GECODE_ME_CHECK(x[i].le(home, val));
00175       }
00176     }
00177 
00178     // Constrain y to be in {min..max}
00179     GECODE_ME_CHECK(y.gq(home, min));
00180     GECODE_ME_CHECK(y.lq(home, max));
00181 
00182     // At least the y.min() last values have value val
00183     for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
00184       GECODE_ME_CHECK(x[pos].eq(home, val));
00185     }
00186     
00187     return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00188   }
00189 
00192   void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
00193     ViewArray<Int::IntView> vx(home, x);
00194     Int::IntView vy(y);
00195     GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
00196   }
00197 
00198 }
00199 
00200 
00212 class CarSequencing : public Script {
00213 public:
00215   enum {
00216     BRANCH_INORDER,  
00217     BRANCH_MIDDLE  
00218   };
00220   enum {
00221     PROP_REGULAR,  
00222     PROP_CUSTOM    
00223   };
00224 protected:
00226   const int problem;
00228   const int ncars;
00230   const int noptions; 
00232   const int nclasses;
00234   const int maxstall;
00236   const int stallval;
00238   const int endval;
00240   IntVar nstall;
00242   IntVar nend;
00244   IntVarArray s;
00245 public:
00247   CarSequencing(const CarOptions& opt)
00248     : problem(opt.size()),
00249       ncars(problems[problem][0]), 
00250       noptions(problems[problem][1]), 
00251       nclasses(problems[problem][2]),
00252       maxstall(opt.maxstall()),
00253       stallval(nclasses),
00254       endval(nclasses+1),
00255       nstall(*this, 0, maxstall),
00256       nend(*this, 0, maxstall),
00257       s(*this, ncars+maxstall, 0, nclasses+1)
00258   {
00259     // Read problem
00260     const int* probit = problems[problem] + 3;
00261 
00262     // Sequence requirements for the options.
00263     IntArgs max(noptions), block(noptions);
00264     for (int i = 0; i < noptions; ++i ) {
00265       max[i] = *probit++;
00266     }
00267     for (int i = 0; i < noptions; ++i ) {
00268       block[i] = *probit++;
00269     }
00270     // Number of cars per class
00271     IntArgs ncc(nclasses);
00272     // What classes require an option
00273     IntSetArgs classes(noptions);
00274     int** cdata = new int*[noptions]; 
00275     for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00276     int* n = new int[noptions];
00277     for (int i = noptions; i--; ) n[i] = 0;
00278     // Read data
00279     for (int c = 0; c < nclasses; ++c) {
00280       probit++;
00281       ncc[c] = *probit++;
00282       for (int o = 0; o < noptions; ++o) {
00283         if (*probit++) {
00284           cdata[o][n[o]++] = c;
00285         }
00286       }
00287     }
00288     // Transfer specification data to int-sets
00289     for (int o = noptions; o--; ) {
00290       classes[o] = IntSet(cdata[o], n[o]);
00291       delete [] cdata[o];
00292     }
00293     delete [] cdata;
00294     delete [] n;
00295 
00296     // Count the cars
00297     {
00298       IntSetArgs c(nclasses+2);
00299       for (int i = nclasses; i--; ) {
00300         c[i] = IntSet(ncc[i], ncc[i]);
00301       }
00302       c[stallval] = IntSet(0, maxstall);
00303       c[  endval] = IntSet(0, maxstall);
00304       count(*this, s, c);
00305     }
00306 
00307     // Count number of end and stalls
00308     count(*this, s, stallval, IRT_EQ, nstall);
00309     count(*this, s,   endval, IRT_EQ,   nend);
00310     rel(*this, nstall+nend == maxstall);
00311 
00312     // Make sure nothing is overloaded
00313     IntSet one(1, 1);
00314     for (int o = noptions; o--; ) {
00315       // sb[i] reflects if car s[i] has option o
00316       BoolVarArgs sb(s.size());
00317       for (int i = s.size(); i--; ) {
00318         BoolVar b(*this, 0, 1);
00319         dom(*this, s[i], classes[o], b);
00320         sb[i] = b;
00321       }
00322       sequence(*this, sb, one, block[o], 0, max[o]);
00323     }
00324 
00325     // End-markers located at end only
00326     switch (opt.propagation()) {
00327     case PROP_REGULAR: {
00328       IntArgs notend(nclasses), notstallend(nclasses+1);
00329       for (int i = nclasses; i--; ) {
00330         notend[i] = i;
00331         notstallend[i] = i;
00332       }
00333       notstallend[nclasses] = stallval;
00334       REG r = *REG(notend) + REG(notstallend) + *REG(endval);
00335       extensional(*this, s, r);
00336       for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
00337         rel(*this, (nend > i) >> (s[pos]==endval));
00338       }
00339     } break;
00340     case PROP_CUSTOM: {
00341       pushtoend(*this, s, nend, endval);
00342     } break;
00343     }
00344     
00345 
00346     // Branching
00347     switch (opt.branching()) {
00348     case BRANCH_INORDER:
00349       branch(*this, s, INT_VAR_NONE(), INT_VAL_MIN());
00350       break;
00351     case BRANCH_MIDDLE: {
00352       IntVarArgs m(s.size());
00353       int mid = s.size() / 2;
00354       int pos = 0;
00355       m[pos++] = s[mid];
00356       for (int i = 1; i <= m.size()/2; ++i) {
00357         if (mid-i >= 0)
00358           m[pos++] = s[mid-i];
00359         if (mid+i < s.size())
00360           m[pos++] = s[mid+i];
00361       }
00362       assert(pos == m.size());
00363       branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
00364       break;
00365     }
00366     }
00367   }
00368         
00370   virtual void constrain(const Space& _best) {
00371     const CarSequencing& best = static_cast<const CarSequencing&>(_best);
00372     rel(*this, nstall, IRT_LE, best.nstall.val());
00373   }
00374 
00376   virtual void
00377   print(std::ostream& os) const {
00378     int width = nclasses > 9 ? 2 : 1;
00379     const char* space = nclasses > 9 ? " " : "";
00380     os << "Stall slots=" << nstall 
00381        << ", End slots=" << nend << std::endl;
00382     int i = 0;
00383     for (; i < s.size(); ++i) {
00384       if (s[i].assigned()) {
00385         int v = s[i].val();
00386         if (v == endval) break;
00387         if (v == stallval) os << space << "_ ";
00388         else               os << std::setw(width) << v << " ";
00389       } else {
00390         os << space << "? ";    
00391       }
00392       if ((i+1)%20 == 0) os << std::endl;
00393     }
00394     if (i%20)
00395       os << std::endl;
00396     os << std::endl;
00397   }
00398 
00400   CarSequencing(bool share, CarSequencing& cs)
00401     : Script(share,cs), 
00402       problem(cs.problem),
00403       ncars(cs.ncars),
00404       noptions(cs.noptions),
00405       nclasses(cs.nclasses),
00406       maxstall(cs.maxstall),
00407       stallval(cs.stallval),
00408       endval(cs.endval)
00409   {
00410     nstall.update(*this, share, cs.nstall);
00411     nend.update(*this, share, cs.nend);
00412     s.update(*this, share, cs.s);
00413   }
00415   virtual Space*
00416   copy(bool share) {
00417     return new CarSequencing(share,*this);
00418   }
00419 };
00420 
00424 int
00425 main(int argc, char* argv[]) {
00426   CarOptions opt("CarSequencing");
00427   opt.solutions(0);
00428   opt.size(0);
00429   opt.branching(CarSequencing::BRANCH_INORDER);
00430   opt.branching(CarSequencing::BRANCH_INORDER,  "inorder");
00431   opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00432   opt.propagation(CarSequencing::PROP_CUSTOM);
00433   opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00434   opt.propagation(CarSequencing::PROP_CUSTOM,  "custom");
00435   opt.parse(argc,argv);
00436   if (opt.size() >= n_problems) {
00437     std::cerr << "Error: size must be between 0 and "
00438               << n_problems-1 << std::endl;
00439     return 1;
00440   }
00441 
00442   Script::run<CarSequencing,BAB,CarOptions>(opt);
00443   return 0;
00444 }
00445 
00446 
00447 namespace {
00449 
00451   const int p0[] = {
00452     10, 5, 6,
00453     1, 2, 1, 2, 1,
00454     2, 3, 3, 5, 5,
00455     0, 1, 1, 0, 1, 1, 0, 
00456     1, 1, 0, 0, 0, 1, 0, 
00457     2, 2, 0, 1, 0, 0, 1, 
00458     3, 2, 0, 1, 0, 1, 0, 
00459     4, 2, 1, 0, 1, 0, 0, 
00460     5, 2, 1, 1, 0, 0, 0
00461   };
00462 
00463   // ---------------------------------
00464   //  Problem 4/72  (Regin & Puget   // 1)
00465   // ---------------------------------
00466   const int p1[] = {
00467     100, 5, 22,
00468     1, 2, 1, 2, 1,
00469     2, 3, 3, 5, 5,
00470     0, 6, 1, 0, 0, 1, 0, 
00471     1, 10, 1, 1, 1, 0, 0, 
00472     2, 2, 1, 1, 0, 0, 1, 
00473     3, 2, 0, 1, 1, 0, 0, 
00474     4, 8, 0, 0, 0, 1, 0, 
00475     5, 15, 0, 1, 0, 0, 0, 
00476     6, 1, 0, 1, 1, 1, 0, 
00477     7, 5, 0, 0, 1, 1, 0, 
00478     8, 2, 1, 0, 1, 1, 0, 
00479     9, 3, 0, 0, 1, 0, 0, 
00480     10, 2, 1, 0, 1, 0, 0, 
00481     11, 1, 1, 1, 1, 0, 1, 
00482     12, 8, 0, 1, 0, 1, 0, 
00483     13, 3, 1, 0, 0, 1, 1, 
00484     14, 10, 1, 0, 0, 0, 0, 
00485     15, 4, 0, 1, 0, 0, 1, 
00486     16, 4, 0, 0, 0, 0, 1, 
00487     17, 2, 1, 0, 0, 0, 1, 
00488     18, 4, 1, 1, 0, 0, 0, 
00489     19, 6, 1, 1, 0, 1, 0, 
00490     20, 1, 1, 0, 1, 0, 1, 
00491     21, 1, 1, 1, 1, 1, 1, 
00492   };
00493 
00494   // --------------------------------
00495   //  Problem 6/76, (Regin & Puget   // 2)
00496   // --------------------------------
00497   const int p2[] = {
00498     100, 5, 22,
00499     1, 2, 1, 2, 1,
00500     2, 3, 3, 5, 5,
00501     0, 13, 1, 0, 0, 0, 0, 
00502     1, 8, 0, 0, 0, 1, 0, 
00503     2, 7, 0, 1, 0, 0, 0, 
00504     3, 1, 1, 0, 0, 1, 0, 
00505     4, 12, 0, 0, 1, 0, 0, 
00506     5, 5, 0, 1, 0, 1, 0, 
00507     6, 5, 0, 0, 1, 1, 0, 
00508     7, 6, 0, 1, 1, 0, 0, 
00509     8, 3, 1, 0, 0, 0, 1, 
00510     9, 12, 1, 1, 0, 0, 0, 
00511     10, 8, 1, 1, 0, 1, 0, 
00512     11, 2, 1, 0, 0, 1, 1, 
00513     12, 2, 1, 1, 1, 0, 0, 
00514     13, 1, 0, 1, 0, 1, 1, 
00515     14, 4, 1, 0, 1, 0, 0, 
00516     15, 4, 0, 1, 0, 0, 1, 
00517     16, 1, 1, 1, 0, 1, 1, 
00518     17, 2, 1, 0, 1, 1, 0, 
00519     18, 1, 0, 0, 0, 0, 1, 
00520     19, 1, 1, 1, 1, 1, 0, 
00521     20, 1, 1, 1, 0, 0, 1, 
00522     21, 1, 0, 1, 1, 1, 0, 
00523   };
00524 
00525   // ---------------------------------
00526   //  Problem 10/93, (Regin & Puget   // 3)
00527   // ---------------------------------
00528   const int p3[] = {
00529     100, 5, 25,
00530     1, 2, 1, 2, 1,
00531     2, 3, 3, 5, 5,
00532     0, 7, 1, 0, 0, 1, 0,
00533     1, 11, 1, 1, 0, 0, 0,
00534     2, 1, 0, 1, 1, 1, 1,
00535     3, 3, 1, 0, 1, 0, 0,
00536     4, 15, 0, 1, 0, 0, 0,
00537     5, 2, 1, 0, 1, 1, 0,
00538     6, 8, 0, 1, 0, 1, 0,
00539     7, 5, 0, 0, 1, 0, 0,
00540     8, 3, 0, 0, 0, 1, 0,
00541     9, 4, 0, 1, 1, 1, 0,
00542     10, 5, 1, 0, 0, 0, 0,
00543     11, 2, 1, 1, 1, 0, 1,
00544     12, 6, 0, 1, 1, 0, 0,
00545     13, 2, 0, 0, 1, 0, 1,
00546     14, 2, 0, 1, 0, 0, 1,
00547     15, 4, 1, 1, 1, 1, 0,
00548     16, 3, 1, 0, 0, 0, 1,
00549     17, 5, 1, 1, 0, 1, 0,
00550     18, 2, 1, 1, 1, 0, 0,
00551     19, 4, 1, 1, 0, 0, 1,
00552     20, 1, 1, 0, 0, 1, 1,
00553     21, 1, 1, 1, 0, 1, 1,
00554     22, 1, 0, 1, 0, 1, 1,
00555     23, 1, 0, 1, 1, 0, 1,
00556     24, 2, 0, 0, 0, 0, 1,
00557   };
00558 
00559   // --------------
00560   //  Problem 16/81,
00561   // --------------
00562   const int p4[] = {
00563     100, 5, 26,
00564     1, 2, 1, 2, 1,
00565     2, 3, 3, 5, 5,
00566     0, 10, 1, 0, 0, 0, 0,
00567     1, 2, 0, 0, 0, 0, 1,
00568     2, 8, 0, 1, 0, 1, 0,
00569     3, 8, 0, 0, 0, 1, 0,
00570     4, 6, 0, 1, 1, 0, 0,
00571     5, 11, 0, 1, 0, 0, 0,
00572     6, 3, 0, 0, 1, 0, 0,
00573     7, 2, 0, 0, 1, 1, 0,
00574     8, 7, 1, 1, 0, 0, 0,
00575     9, 2, 1, 0, 0, 1, 1,
00576     10, 4, 1, 0, 1, 0, 0,
00577     11, 7, 1, 0, 0, 1, 0,
00578     12, 1, 1, 1, 1, 0, 1,
00579     13, 3, 0, 1, 1, 1, 0,
00580     14, 4, 0, 1, 0, 0, 1,
00581     15, 5, 1, 1, 1, 0, 0,
00582     16, 2, 1, 1, 0, 0, 1,
00583     17, 1, 1, 0, 1, 1, 1,
00584     18, 2, 1, 0, 1, 1, 0,
00585     19, 3, 1, 0, 0, 0, 1,
00586     20, 2, 0, 1, 1, 0, 1,
00587     21, 1, 0, 1, 0, 1, 1,
00588     22, 3, 1, 1, 0, 1, 0,
00589     23, 1, 0, 0, 1, 1, 1,
00590     24, 1, 1, 1, 1, 1, 1,
00591     25, 1, 1, 1, 1, 1, 0,
00592   };
00593 
00594   // ----------------------------------
00595   //  Problem 19/71,  (Regin & Puget   // 4)
00596   // ----------------------------------
00597   const int p5[] = {
00598     100, 5, 23,
00599     1, 2, 1, 2, 1,
00600     2, 3, 3, 5, 5,
00601     0, 2, 0, 0, 0, 1, 1,
00602     1, 2, 0, 0, 1, 0, 1,
00603     2, 5, 0, 1, 1, 1, 0,
00604     3, 4, 0, 0, 0, 1, 0,
00605     4, 4, 0, 1, 0, 1, 0,
00606     5, 1, 1, 1, 0, 0, 1,
00607     6, 3, 1, 1, 1, 0, 1,
00608     7, 4, 0, 0, 1, 0, 0,
00609     8, 19, 0, 1, 0, 0, 0,
00610     9, 7, 1, 1, 0, 1, 0,
00611     10, 10, 1, 0, 0, 0, 0,
00612     11, 1, 0, 0, 1, 1, 0,
00613     12, 5, 1, 1, 1, 1, 0,
00614     13, 2, 1, 0, 1, 1, 0,
00615     14, 6, 1, 1, 0, 0, 0,
00616     15, 4, 1, 1, 1, 0, 0,
00617     16, 8, 1, 0, 0, 1, 0,
00618     17, 1, 1, 0, 0, 0, 1,
00619     18, 4, 0, 1, 1, 0, 0,
00620     19, 2, 0, 0, 0, 0, 1,
00621     20, 4, 0, 1, 0, 0, 1,
00622     21, 1, 1, 1, 0, 1, 1,
00623     22, 1, 0, 1, 1, 0, 1,
00624   };
00625 
00626   const int* problems[] = {
00627     &p0[0],
00628     &p1[0],
00629     &p2[0],
00630     &p3[0],
00631     &p4[0],
00632     &p5[0],
00633   };
00634 
00636   const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00637 };
00638 
00639 // STATISTICS: example-any
00640