Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037 
00038 #include <iomanip>
00039 
00040 using namespace Gecode;
00041 
00042 // Problems
00043 namespace {
00044   // Problem data
00045   extern const int* problems[];
00046   // Number of problems
00047   extern const unsigned int n_problems;
00048 }
00049 
00050 namespace {
00056   class CarOptions : public SizeOptions {
00057   private:
00059     Driver::UnsignedIntOption _maxstall;
00060 
00061   public:
00063     CarOptions(const char* s)
00064       : SizeOptions(s),
00065         _maxstall("maxstall", "Maximum numbere of stalls", 30)
00066     {
00067       // Add options
00068       add(_maxstall);
00069     }
00071     void parse(int& argc, char* argv[]) {
00072       SizeOptions::parse(argc,argv);
00073     }
00075     int maxstall(void) const { return _maxstall.value(); }
00076   };
00077 
00078 
00096   template <class View>
00097   class PushToEnd : public NaryOnePropagator<View,Int::PC_INT_BND> {
00098   protected:
00099     using NaryOnePropagator<View,Int::PC_INT_BND>::x;
00100     using NaryOnePropagator<View,Int::PC_INT_BND>::y;
00101     int val;
00102 
00104     PushToEnd(Space& home, PushToEnd& p);
00106     PushToEnd(Space& home, ViewArray<View>& x0, View y0, int val0);
00107   public:
00109     PushToEnd(Space& home, Propagator& p,
00110               ViewArray<View>& x0, View y0, int val0);
00112     virtual Actor* copy(Space& home);
00114     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00116     static  ExecStatus post(Space& home,
00117                             ViewArray<View>& x0, View y0, int val0);
00118   };
00119 
00120   template <class View>
00121   inline
00122   PushToEnd<View>::PushToEnd(Space& home,
00123                              ViewArray<View>& x0, View y0, int val0)
00124     : NaryOnePropagator<View,Int::PC_INT_BND>(home,x0,y0), val(val0) {}
00125 
00126   template <class View>
00127   ExecStatus
00128   PushToEnd<View>::post(Space& home,
00129                         ViewArray<View>& x0, View y0, int val0) {
00130     (void) new (home) PushToEnd<View>(home,x0,y0,val0);
00131     return ES_OK;
00132   }
00133 
00134   template <class View>
00135   inline
00136   PushToEnd<View>::PushToEnd(Space& home, PushToEnd<View>& p)
00137     : NaryOnePropagator<View,Int::PC_INT_BND>(home,p), val(p.val) {}
00138 
00139   template <class View>
00140   inline
00141   PushToEnd<View>::PushToEnd(Space& home, Propagator& p,
00142                              ViewArray<View>& x0, View y0, int val0)
00143   : NaryOnePropagator<View,Int::PC_INT_BND>(home,p,x0,y0), val(val0) {}
00144 
00145   template <class View>
00146   Actor*
00147   PushToEnd<View>::copy(Space& home) {
00148     return new (home) PushToEnd<View>(home,*this);
00149   }
00150 
00151   template <class View>
00152   ExecStatus
00153   PushToEnd<View>::propagate(Space& home, const ModEventDelta&) {
00154     // Find number of required positions
00155     int min = 0;
00156     for (int i = x.size(); i-- && x[i].min() >= val-1; ) {
00157       ++min;
00158     }
00159     // Find number of possible positions
00160     int max = 0;
00161     {
00162       int i = x.size();
00163       while (i--) {
00164         if (x[i].max() != val) break;
00165         ++max;
00166         if (max >= y.max()) break;
00167       }
00168       // No variables later than max can have value val
00169       while (i--) {
00170         GECODE_ME_CHECK(x[i].le(home, val));
00171       }
00172     }
00173 
00174     // Constrain y to be in {min..max}
00175     GECODE_ME_CHECK(y.gq(home, min));
00176     GECODE_ME_CHECK(y.lq(home, max));
00177 
00178     // At least the y.min() last values have value val
00179     for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
00180       GECODE_ME_CHECK(x[pos].eq(home, val));
00181     }
00182 
00183     return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00184   }
00185 
00188   void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
00189     ViewArray<Int::IntView> vx(home, x);
00190     Int::IntView vy(y);
00191     GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
00192   }
00193 
00194 }
00195 
00196 
00208 class CarSequencing : public Script {
00209 public:
00211   enum {
00212     BRANCH_INORDER,  
00213     BRANCH_MIDDLE  
00214   };
00216   enum {
00217     PROP_REGULAR,  
00218     PROP_CUSTOM    
00219   };
00220 protected:
00222   const int problem;
00224   const int ncars;
00226   const int noptions;
00228   const int nclasses;
00230   const int maxstall;
00232   const int stallval;
00234   const int endval;
00236   IntVar nstall;
00238   IntVar nend;
00240   IntVarArray s;
00241 public:
00243   CarSequencing(const CarOptions& opt)
00244     : Script(opt),
00245       problem(opt.size()),
00246       ncars(problems[problem][0]),
00247       noptions(problems[problem][1]),
00248       nclasses(problems[problem][2]),
00249       maxstall(opt.maxstall()),
00250       stallval(nclasses),
00251       endval(nclasses+1),
00252       nstall(*this, 0, maxstall),
00253       nend(*this, 0, maxstall),
00254       s(*this, ncars+maxstall, 0, nclasses+1)
00255   {
00256     // Read problem
00257     const int* probit = problems[problem] + 3;
00258 
00259     // Sequence requirements for the options.
00260     IntArgs max(noptions), block(noptions);
00261     for (int i = 0; i < noptions; ++i ) {
00262       max[i] = *probit++;
00263     }
00264     for (int i = 0; i < noptions; ++i ) {
00265       block[i] = *probit++;
00266     }
00267     // Number of cars per class
00268     IntArgs ncc(nclasses);
00269     // What classes require an option
00270     IntSetArgs classes(noptions);
00271     int** cdata = new int*[noptions];
00272     for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
00273     int* n = new int[noptions];
00274     for (int i = noptions; i--; ) n[i] = 0;
00275     // Read data
00276     for (int c = 0; c < nclasses; ++c) {
00277       probit++;
00278       ncc[c] = *probit++;
00279       for (int o = 0; o < noptions; ++o) {
00280         if (*probit++) {
00281           cdata[o][n[o]++] = c;
00282         }
00283       }
00284     }
00285     // Transfer specification data to int-sets
00286     for (int o = noptions; o--; ) {
00287       classes[o] = IntSet(cdata[o], n[o]);
00288       delete [] cdata[o];
00289     }
00290     delete [] cdata;
00291     delete [] n;
00292 
00293     // Count the cars
00294     {
00295       IntSetArgs c(nclasses+2);
00296       for (int i = nclasses; i--; ) {
00297         c[i] = IntSet(ncc[i], ncc[i]);
00298       }
00299       c[stallval] = IntSet(0, maxstall);
00300       c[  endval] = IntSet(0, maxstall);
00301       count(*this, s, c);
00302     }
00303 
00304     // Count number of end and stalls
00305     count(*this, s, stallval, IRT_EQ, nstall);
00306     count(*this, s,   endval, IRT_EQ,   nend);
00307     rel(*this, nstall+nend == maxstall);
00308 
00309     // Make sure nothing is overloaded
00310     IntSet one(1, 1);
00311     for (int o = noptions; o--; ) {
00312       // sb[i] reflects if car s[i] has option o
00313       BoolVarArgs sb(s.size());
00314       for (int i = s.size(); i--; ) {
00315         BoolVar b(*this, 0, 1);
00316         dom(*this, s[i], classes[o], b);
00317         sb[i] = b;
00318       }
00319       sequence(*this, sb, one, block[o], 0, max[o]);
00320     }
00321 
00322     // End-markers located at end only
00323     switch (opt.propagation()) {
00324     case PROP_REGULAR: {
00325       IntArgs notend(nclasses), notstallend(nclasses+1);
00326       for (int i = nclasses; i--; ) {
00327         notend[i] = i;
00328         notstallend[i] = i;
00329       }
00330       notstallend[nclasses] = stallval;
00331       REG r = *REG(notend) + REG(notstallend) + *REG(endval);
00332       extensional(*this, s, r);
00333       for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
00334         rel(*this, (nend > i) >> (s[pos]==endval));
00335       }
00336     } break;
00337     case PROP_CUSTOM: {
00338       pushtoend(*this, s, nend, endval);
00339     } break;
00340     }
00341 
00342 
00343     // Branching
00344     switch (opt.branching()) {
00345     case BRANCH_INORDER:
00346       branch(*this, s, INT_VAR_NONE(), INT_VAL_MIN());
00347       break;
00348     case BRANCH_MIDDLE: {
00349       IntVarArgs m(s.size());
00350       int mid = s.size() / 2;
00351       int pos = 0;
00352       m[pos++] = s[mid];
00353       for (int i = 1; i <= m.size()/2; ++i) {
00354         if (mid-i >= 0)
00355           m[pos++] = s[mid-i];
00356         if (mid+i < s.size())
00357           m[pos++] = s[mid+i];
00358       }
00359       assert(pos == m.size());
00360       branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
00361       break;
00362     }
00363     }
00364   }
00365 
00367   virtual void constrain(const Space& _best) {
00368     const CarSequencing& best = static_cast<const CarSequencing&>(_best);
00369     rel(*this, nstall, IRT_LE, best.nstall.val());
00370   }
00371 
00373   virtual void
00374   print(std::ostream& os) const {
00375     int width = nclasses > 9 ? 2 : 1;
00376     const char* space = nclasses > 9 ? " " : "";
00377     os << "Stall slots=" << nstall
00378        << ", End slots=" << nend << std::endl;
00379     int i = 0;
00380     for (; i < s.size(); ++i) {
00381       if (s[i].assigned()) {
00382         int v = s[i].val();
00383         if (v == endval) break;
00384         if (v == stallval) os << space << "_ ";
00385         else               os << std::setw(width) << v << " ";
00386       } else {
00387         os << space << "? ";
00388       }
00389       if ((i+1)%20 == 0) os << std::endl;
00390     }
00391     if (i%20)
00392       os << std::endl;
00393     os << std::endl;
00394   }
00395 
00397   CarSequencing(CarSequencing& cs)
00398     : Script(cs),
00399       problem(cs.problem),
00400       ncars(cs.ncars),
00401       noptions(cs.noptions),
00402       nclasses(cs.nclasses),
00403       maxstall(cs.maxstall),
00404       stallval(cs.stallval),
00405       endval(cs.endval)
00406   {
00407     nstall.update(*this, cs.nstall);
00408     nend.update(*this, cs.nend);
00409     s.update(*this, cs.s);
00410   }
00412   virtual Space*
00413   copy(void) {
00414     return new CarSequencing(*this);
00415   }
00416 };
00417 
00421 int
00422 main(int argc, char* argv[]) {
00423   CarOptions opt("CarSequencing");
00424   opt.solutions(0);
00425   opt.size(0);
00426   opt.branching(CarSequencing::BRANCH_INORDER);
00427   opt.branching(CarSequencing::BRANCH_INORDER,  "inorder");
00428   opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
00429   opt.propagation(CarSequencing::PROP_CUSTOM);
00430   opt.propagation(CarSequencing::PROP_REGULAR, "regular");
00431   opt.propagation(CarSequencing::PROP_CUSTOM,  "custom");
00432   opt.parse(argc,argv);
00433   if (opt.size() >= n_problems) {
00434     std::cerr << "Error: size must be between 0 and "
00435               << n_problems-1 << std::endl;
00436     return 1;
00437   }
00438 
00439   Script::run<CarSequencing,BAB,CarOptions>(opt);
00440   return 0;
00441 }
00442 
00443 
00444 namespace {
00446 
00448   const int p0[] = {
00449     10, 5, 6,
00450     1, 2, 1, 2, 1,
00451     2, 3, 3, 5, 5,
00452     0, 1, 1, 0, 1, 1, 0,
00453     1, 1, 0, 0, 0, 1, 0,
00454     2, 2, 0, 1, 0, 0, 1,
00455     3, 2, 0, 1, 0, 1, 0,
00456     4, 2, 1, 0, 1, 0, 0,
00457     5, 2, 1, 1, 0, 0, 0
00458   };
00459 
00460   // ---------------------------------
00461   //  Problem 4/72  (Regin & Puget   // 1)
00462   // ---------------------------------
00463   const int p1[] = {
00464     100, 5, 22,
00465     1, 2, 1, 2, 1,
00466     2, 3, 3, 5, 5,
00467     0, 6, 1, 0, 0, 1, 0,
00468     1, 10, 1, 1, 1, 0, 0,
00469     2, 2, 1, 1, 0, 0, 1,
00470     3, 2, 0, 1, 1, 0, 0,
00471     4, 8, 0, 0, 0, 1, 0,
00472     5, 15, 0, 1, 0, 0, 0,
00473     6, 1, 0, 1, 1, 1, 0,
00474     7, 5, 0, 0, 1, 1, 0,
00475     8, 2, 1, 0, 1, 1, 0,
00476     9, 3, 0, 0, 1, 0, 0,
00477     10, 2, 1, 0, 1, 0, 0,
00478     11, 1, 1, 1, 1, 0, 1,
00479     12, 8, 0, 1, 0, 1, 0,
00480     13, 3, 1, 0, 0, 1, 1,
00481     14, 10, 1, 0, 0, 0, 0,
00482     15, 4, 0, 1, 0, 0, 1,
00483     16, 4, 0, 0, 0, 0, 1,
00484     17, 2, 1, 0, 0, 0, 1,
00485     18, 4, 1, 1, 0, 0, 0,
00486     19, 6, 1, 1, 0, 1, 0,
00487     20, 1, 1, 0, 1, 0, 1,
00488     21, 1, 1, 1, 1, 1, 1,
00489   };
00490 
00491   // --------------------------------
00492   //  Problem 6/76, (Regin & Puget   // 2)
00493   // --------------------------------
00494   const int p2[] = {
00495     100, 5, 22,
00496     1, 2, 1, 2, 1,
00497     2, 3, 3, 5, 5,
00498     0, 13, 1, 0, 0, 0, 0,
00499     1, 8, 0, 0, 0, 1, 0,
00500     2, 7, 0, 1, 0, 0, 0,
00501     3, 1, 1, 0, 0, 1, 0,
00502     4, 12, 0, 0, 1, 0, 0,
00503     5, 5, 0, 1, 0, 1, 0,
00504     6, 5, 0, 0, 1, 1, 0,
00505     7, 6, 0, 1, 1, 0, 0,
00506     8, 3, 1, 0, 0, 0, 1,
00507     9, 12, 1, 1, 0, 0, 0,
00508     10, 8, 1, 1, 0, 1, 0,
00509     11, 2, 1, 0, 0, 1, 1,
00510     12, 2, 1, 1, 1, 0, 0,
00511     13, 1, 0, 1, 0, 1, 1,
00512     14, 4, 1, 0, 1, 0, 0,
00513     15, 4, 0, 1, 0, 0, 1,
00514     16, 1, 1, 1, 0, 1, 1,
00515     17, 2, 1, 0, 1, 1, 0,
00516     18, 1, 0, 0, 0, 0, 1,
00517     19, 1, 1, 1, 1, 1, 0,
00518     20, 1, 1, 1, 0, 0, 1,
00519     21, 1, 0, 1, 1, 1, 0,
00520   };
00521 
00522   // ---------------------------------
00523   //  Problem 10/93, (Regin & Puget   // 3)
00524   // ---------------------------------
00525   const int p3[] = {
00526     100, 5, 25,
00527     1, 2, 1, 2, 1,
00528     2, 3, 3, 5, 5,
00529     0, 7, 1, 0, 0, 1, 0,
00530     1, 11, 1, 1, 0, 0, 0,
00531     2, 1, 0, 1, 1, 1, 1,
00532     3, 3, 1, 0, 1, 0, 0,
00533     4, 15, 0, 1, 0, 0, 0,
00534     5, 2, 1, 0, 1, 1, 0,
00535     6, 8, 0, 1, 0, 1, 0,
00536     7, 5, 0, 0, 1, 0, 0,
00537     8, 3, 0, 0, 0, 1, 0,
00538     9, 4, 0, 1, 1, 1, 0,
00539     10, 5, 1, 0, 0, 0, 0,
00540     11, 2, 1, 1, 1, 0, 1,
00541     12, 6, 0, 1, 1, 0, 0,
00542     13, 2, 0, 0, 1, 0, 1,
00543     14, 2, 0, 1, 0, 0, 1,
00544     15, 4, 1, 1, 1, 1, 0,
00545     16, 3, 1, 0, 0, 0, 1,
00546     17, 5, 1, 1, 0, 1, 0,
00547     18, 2, 1, 1, 1, 0, 0,
00548     19, 4, 1, 1, 0, 0, 1,
00549     20, 1, 1, 0, 0, 1, 1,
00550     21, 1, 1, 1, 0, 1, 1,
00551     22, 1, 0, 1, 0, 1, 1,
00552     23, 1, 0, 1, 1, 0, 1,
00553     24, 2, 0, 0, 0, 0, 1,
00554   };
00555 
00556   // --------------
00557   //  Problem 16/81,
00558   // --------------
00559   const int p4[] = {
00560     100, 5, 26,
00561     1, 2, 1, 2, 1,
00562     2, 3, 3, 5, 5,
00563     0, 10, 1, 0, 0, 0, 0,
00564     1, 2, 0, 0, 0, 0, 1,
00565     2, 8, 0, 1, 0, 1, 0,
00566     3, 8, 0, 0, 0, 1, 0,
00567     4, 6, 0, 1, 1, 0, 0,
00568     5, 11, 0, 1, 0, 0, 0,
00569     6, 3, 0, 0, 1, 0, 0,
00570     7, 2, 0, 0, 1, 1, 0,
00571     8, 7, 1, 1, 0, 0, 0,
00572     9, 2, 1, 0, 0, 1, 1,
00573     10, 4, 1, 0, 1, 0, 0,
00574     11, 7, 1, 0, 0, 1, 0,
00575     12, 1, 1, 1, 1, 0, 1,
00576     13, 3, 0, 1, 1, 1, 0,
00577     14, 4, 0, 1, 0, 0, 1,
00578     15, 5, 1, 1, 1, 0, 0,
00579     16, 2, 1, 1, 0, 0, 1,
00580     17, 1, 1, 0, 1, 1, 1,
00581     18, 2, 1, 0, 1, 1, 0,
00582     19, 3, 1, 0, 0, 0, 1,
00583     20, 2, 0, 1, 1, 0, 1,
00584     21, 1, 0, 1, 0, 1, 1,
00585     22, 3, 1, 1, 0, 1, 0,
00586     23, 1, 0, 0, 1, 1, 1,
00587     24, 1, 1, 1, 1, 1, 1,
00588     25, 1, 1, 1, 1, 1, 0,
00589   };
00590 
00591   // ----------------------------------
00592   //  Problem 19/71,  (Regin & Puget   // 4)
00593   // ----------------------------------
00594   const int p5[] = {
00595     100, 5, 23,
00596     1, 2, 1, 2, 1,
00597     2, 3, 3, 5, 5,
00598     0, 2, 0, 0, 0, 1, 1,
00599     1, 2, 0, 0, 1, 0, 1,
00600     2, 5, 0, 1, 1, 1, 0,
00601     3, 4, 0, 0, 0, 1, 0,
00602     4, 4, 0, 1, 0, 1, 0,
00603     5, 1, 1, 1, 0, 0, 1,
00604     6, 3, 1, 1, 1, 0, 1,
00605     7, 4, 0, 0, 1, 0, 0,
00606     8, 19, 0, 1, 0, 0, 0,
00607     9, 7, 1, 1, 0, 1, 0,
00608     10, 10, 1, 0, 0, 0, 0,
00609     11, 1, 0, 0, 1, 1, 0,
00610     12, 5, 1, 1, 1, 1, 0,
00611     13, 2, 1, 0, 1, 1, 0,
00612     14, 6, 1, 1, 0, 0, 0,
00613     15, 4, 1, 1, 1, 0, 0,
00614     16, 8, 1, 0, 0, 1, 0,
00615     17, 1, 1, 0, 0, 0, 1,
00616     18, 4, 0, 1, 1, 0, 0,
00617     19, 2, 0, 0, 0, 0, 1,
00618     20, 4, 0, 1, 0, 0, 1,
00619     21, 1, 1, 1, 0, 1, 1,
00620     22, 1, 0, 1, 1, 0, 1,
00621   };
00622 
00623   const int* problems[] = {
00624     &p0[0],
00625     &p1[0],
00626     &p2[0],
00627     &p3[0],
00628     &p4[0],
00629     &p5[0],
00630   };
00631 
00633   const unsigned int n_problems = sizeof(problems)/sizeof(int*);
00634 };
00635 
00636 // STATISTICS: example-any
00637