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

bacp.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2006
00011  *     Mikael Lagerkvist, 2010
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 #include <gecode/int/branch.hh>
00042 
00043 #include <map>
00044 #include <string>
00045 #include <list>
00046 #include <vector>
00047 
00048 using namespace Gecode;
00049 
00051 class Course {
00052 public:
00053   const char* name; 
00054   int credit;       
00055 };
00056 
00058 class Curriculum {
00059 public:
00061   int p;
00063   int a;
00065   int b;
00067   int c;
00069   int d;
00070 
00072   const Course *courses;
00074   const char **prereqs;
00075 };
00076 
00077 namespace {
00078 
00079   extern const Curriculum curriculum[];
00080   extern const unsigned int n_examples;
00081 
00082 }
00083 
00096 class BACP : public IntMinimizeScript {
00097 protected:
00099   const Curriculum curr;
00100 
00102   IntVarArray l;
00104   IntVar u;
00106   IntVarArray q;
00107 
00109   IntVarArray x;
00110 public:
00112   enum {
00113     BRANCHING_NAIVE,    
00114     BRANCHING_LOAD,     
00115     BRANCHING_LOAD_REV, 
00116   };
00117 
00119   BACP(const SizeOptions& opt)
00120     : IntMinimizeScript(opt), curr(curriculum[opt.size()]) {
00121     std::map<std::string, int> courseMap; // Map names to course numbers
00122     int maxCredit = 0;
00123     int numberOfCourses = 0;
00124     for (const Course* co=curr.courses; co->name != 0; co++) {
00125       courseMap[co->name] = numberOfCourses++;
00126       maxCredit += co->credit;
00127     }
00128 
00129     int p = curr.p;
00130     int a = curr.a;
00131     int b = curr.b;
00132     int c = curr.c;
00133     int d = curr.d;
00134 
00135     l = IntVarArray(*this, p, a, b);
00136     u = IntVar(*this, 0, maxCredit);
00137     q = IntVarArray(*this, p, c, d);
00138     x = IntVarArray(*this, numberOfCourses, 0, p-1);
00139 
00140     for (int j=0; j<p; j++) {
00141       BoolVarArgs xij(*this, numberOfCourses, 0, 1);
00142       IntArgs t(numberOfCourses);
00143       for (int i=0; i<numberOfCourses; i++) {
00144         rel(*this, (x[i]==j) == xij[i]);
00145         t[i] = curr.courses[i].credit;
00146       }
00147       // sum over all t*(xi==j) is load of period i
00148       linear(*this, t, xij, IRT_EQ, l[j]);
00149       // sum over all (xi==j) is number of courses in period i
00150       linear(*this, xij, IRT_EQ, q[j]);
00151     }
00152 
00153     // Precedence
00154     for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
00155       rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
00156 
00157     // Optimization criterion: minimize u
00158     max(*this, l, u);
00159 
00160     // Redundant constraints
00161     linear(*this, l, IRT_EQ, maxCredit);
00162     linear(*this, q, IRT_EQ, numberOfCourses);
00163 
00164     switch (opt.branching()) {
00165     case BRANCHING_NAIVE:
00166       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00167       break;
00168     case BRANCHING_LOAD:
00169       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load));
00170       break;
00171     case BRANCHING_LOAD_REV:
00172       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load_rev));
00173       break;
00174     }
00175   }
00177   static int load(const Space& home, IntVar x, int) {
00178     const BACP& b = static_cast<const BACP&>(home);
00179     IntVarValues values(x);
00180     int val = -1;
00181     int best = Int::Limits::max+1;
00182     while (values()) {
00183       if (b.l[values.val()].min() < best) {
00184         val  = values.val();
00185         best = b.l[val].min();
00186       }
00187       ++values;
00188     }
00189     assert(val != -1);
00190     return val;
00191   }
00193   static int load_rev(const Space& home, IntVar x, int) {
00194     const BACP& b = static_cast<const BACP&>(home);
00195     IntVarValues values(x);
00196     int val = -1;
00197     int best = Int::Limits::min-1;
00198     while (values()) {
00199       if (b.l[values.val()].min() > best) {
00200         val  = values.val();
00201         best = b.l[val].min();
00202       }
00203       ++values;
00204     }
00205     assert(val != -1);
00206     return val;
00207   }
00209   BACP(BACP& bacp) : IntMinimizeScript(bacp),
00210     curr(bacp.curr) {
00211     l.update(*this, bacp.l);
00212     u.update(*this, bacp.u);
00213     x.update(*this, bacp.x);
00214   }
00216   virtual Space*
00217   copy(void) {
00218     return new BACP(*this);
00219   }
00221   virtual IntVar cost(void) const {
00222     return u;
00223   }
00225   virtual void
00226   print(std::ostream& os) const {
00227     std::vector<std::list<int> > period(curr.p);
00228     for (int i=x.size(); i--;)
00229       period[x[i].val()].push_back(i);
00230 
00231     os << "Solution with load " << u.val() << ":" << std::endl;
00232     for (int i=0; i<curr.p; i++) {
00233       os << "\tPeriod "<<i+1<<": ";
00234       for (std::list<int>::iterator v=period[i].begin();
00235            v != period[i].end(); ++v) {
00236         os << curr.courses[*v].name << " ";
00237       }
00238       os << std::endl;
00239     }
00240     os << std::endl;
00241   }
00242 
00243 };
00244 
00248 int
00249 main(int argc, char* argv[]) {
00250   SizeOptions opt("BACP");
00251   opt.branching(BACP::BRANCHING_NAIVE);
00252   opt.branching(BACP::BRANCHING_NAIVE,"naive");
00253   opt.branching(BACP::BRANCHING_LOAD,"load");
00254   opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
00255   opt.size(2);
00256   opt.solutions(0);
00257   opt.iterations(20);
00258   opt.parse(argc,argv);
00259   if (opt.size() >= n_examples) {
00260     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00261               << std::endl;
00262     return 1;
00263   }
00264   IntMinimizeScript::run<BACP,BAB,SizeOptions>(opt);
00265   return 0;
00266 }
00267 
00268 namespace {
00274 
00275   const Course courses8[] =
00276     {
00277       {"dew100", 1},
00278       {"fis100", 3},
00279       {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
00280       {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
00281       {"iei134", 3},{"iei141", 3},{"mat194", 4},
00282       {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
00283       {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
00284       {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
00285       {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
00286       {0,0}
00287     };
00288 
00290   const char* prereqs8[] =
00291     {
00292     "dew101","dew100",
00293     "fis101","fis100",
00294     "fis101","mat192",
00295     "mat191","mat190",
00296     "mat193","mat190",
00297     "mat193","mat192",
00298     "fis102","fis101",
00299     "fis102","mat193",
00300     "iei134","iwi131",
00301     "iei141","iwi131",
00302     "mat194","mat191 ",
00303     "mat194","mat193",
00304     "dewxx0","dew101",
00305     "hcw311","hcw310",
00306     "iei132","iei134",
00307     "iei133","iei134",
00308     "iei142","iei141",
00309     "mat195","mat194",
00310     "iei231","iei134",
00311     "iei241","iei142",
00312     "iei271","iei162",
00313     "iei281","mat195",
00314     "iei233","iei231",
00315     "iei238","iei231",
00316     "iei261","iwn261",
00317     "iei272","iei271",
00318     "iei273","iei271",
00319     "iei273","iei271",
00320     "iei161","iwn261",
00321     "iei161","iwn261",
00322     "iei232","iei273",
00323     "iei232","iei273",
00324     "iei262","iwn261",
00325     "iei274","iei273",
00326     "iei274","iei273",
00327     "iei219","iei232",
00328     "iei248","iei233",
00329     "iei248","iei233",
00330     0,0
00331     };
00332 
00334   const Course courses10[] = {
00335   {"dew100",1},
00336   {"fis100",3},
00337   {"hrwxx1",2},
00338   {"iwg101",2},
00339   {"mat021",5},
00340   {"qui010",3},
00341   {"dew101",1},
00342   {"fis110",5},
00343   {"hrwxx2",2},
00344   {"iwi131",3},
00345   {"mat022",5},
00346   {"dewxx0",1},
00347   {"fis120",4},
00348   {"hcw310",1},
00349   {"hrwxx3",2},
00350   {"ili134",4},
00351   {"ili151",3},
00352   {"mat023",4},
00353   {"hcw311",1},
00354   {"ili135",4},
00355   {"ili153",3},
00356   {"ili260",3},
00357   {"iwn261",3},
00358   {"mat024",4},
00359   {"fis130",4},
00360   {"ili239",4},
00361   {"ili245",4},
00362   {"ili253",4},
00363   {"fis140",4},
00364   {"ili236",4},
00365   {"ili243",4},
00366   {"ili270",3},
00367   {"ili280",4},
00368   {"ici344",4},
00369   {"ili263",3},
00370   {"ili332",4},
00371   {"ili355",4},
00372   {"iwn170",3},
00373   {"icdxx1",3},
00374   {"ili362",3},
00375   {"iwn270",3},
00376   {"icdxx2",3},
00377   {0,0}
00378   };
00379 
00381   const char* prereqs10[] = {
00382   "dew101","dew100",
00383   "fis110","fis100",
00384   "fis110","mat021",
00385   "mat022","mat021",
00386   "dewxx0","dew101",
00387   "fis120","fis110",
00388   "fis120","mat022",
00389   "ili134","iwi131",
00390   "ili151","iwi131",
00391   "mat023","mat022",
00392   "hcw311","hcw310",
00393   "ili135","ili134",
00394   "ili153","ili134",
00395   "ili153","ili151",
00396   "mat024","mat023",
00397   "fis130","fis110",
00398   "fis130","mat022",
00399   "ili239","ili135",
00400   "ili245","ili153",
00401   "ili253","ili153",
00402   "fis140","fis120",
00403   "fis140","fis130",
00404   "ili236","ili239",
00405   "ili243","ili245",
00406   "ili270","ili260",
00407   "ili270","iwn261",
00408   "ili280","mat024",
00409   "ici344","ili243",
00410   "ili263","ili260",
00411   "ili263","iwn261",
00412   "ili332","ili236",
00413   "ili355","ili153",
00414   "ili355","ili280",
00415   "ili362","ili263",
00416   0,0
00417   };
00418 
00420   const Course courses12[] = {
00421   {"dew100",1},
00422   {"fis100",3},
00423   {"hcw310",1},
00424   {"iwg101",2},
00425   {"mat111",4},
00426   {"mat121",4},
00427   {"dew101",1},
00428   {"fis110",5},
00429   {"iwi131",3},
00430   {"mat112",4},
00431   {"mat122",4},
00432   {"dewxx0",1},
00433   {"fis120",4},
00434   {"hcw311",1},
00435   {"hxwxx1",1},
00436   {"ili142",4},
00437   {"mat113",4},
00438   {"mat123",4},
00439   {"fis130",4},
00440   {"ili134",4},
00441   {"ili151",3},
00442   {"iwm185",3},
00443   {"mat124",4},
00444   {"fis140",4},
00445   {"hxwxx2",1},
00446   {"ile260",3},
00447   {"ili260",3},
00448   {"iwn170",3},
00449   {"qui104",3},
00450   {"ili231",3},
00451   {"ili243",4},
00452   {"ili252",4},
00453   {"ili273",3},
00454   {"mat210",4},
00455   {"mat260",4},
00456   {"ild208",3},
00457   {"ili221",4},
00458   {"ili274",3},
00459   {"ili281",3},
00460   {"iwn270",3},
00461   {"mat270",4},
00462   {"hrw150",2},
00463   {"ili238",4},
00464   {"ili242",3},
00465   {"ili275",3},
00466   {"ili355",4},
00467   {"hrw110",2},
00468   {"ici393",4},
00469   {"ili237",4},
00470   {"ili334",4},
00471   {"ili363",3},
00472   {"iwn261",3},
00473   {"hrw100",2},
00474   {"ici382",4},
00475   {"ili331",4},
00476   {"ili362",3},
00477   {"ili381",3},
00478   {"iln230",3},
00479   {"ici313",2},
00480   {"ici315",2},
00481   {"ici332",3},
00482   {"ici344",4},
00483   {"icn336",3},
00484   {"iwi365",3},
00485   {"ici314",2},
00486   {"ici367",2},
00487   {0,0}
00488   };
00489 
00491   const char* prereqs12[] = {
00492   "dew101","dew100",
00493   "fis110","fis100",
00494   "fis110","mat121",
00495   "mat112","mat111",
00496   "mat122","mat111",
00497   "mat122","mat121",
00498   "dewxx0","dew101",
00499   "fis120","fis110",
00500   "fis120","mat122",
00501   "hcw311","hcw310",
00502   "ili142","iwi131",
00503   "mat113","mat112",
00504   "mat113","mat122",
00505   "mat123","mat112",
00506   "mat123","mat122",
00507   "fis130","fis110",
00508   "fis130","mat122",
00509   "ili134","iwi131",
00510   "ili151","mat112",
00511   "mat124","mat113",
00512   "mat124","mat123",
00513   "fis140","fis120",
00514   "fis140","fis130",
00515   "ile260","fis120",
00516   "ile260","mat124",
00517   "ili231","iwi131",
00518   "ili252","iwi131",
00519   "ili273","ili260",
00520   "mat210","mat113",
00521   "mat260","iwi131",
00522   "mat260","mat113",
00523   "mat260","mat123",
00524   "ili221","ili134",
00525   "ili221","ili231",
00526   "ili221","mat260",
00527   "ili274","ili273",
00528   "ili281","mat260",
00529   "mat270","iwi131",
00530   "mat270","mat113",
00531   "mat270","mat123",
00532   "ili238","ili134",
00533   "ili242","ili142",
00534   "ili275","ili274",
00535   "ili355","ili221",
00536   "hrw110","hrw150",
00537   "ici393","mat210",
00538   "ici393","mat260",
00539   "ili237","ili231",
00540   "ili237","ili252",
00541   "ili334","ili238",
00542   "ili363","ili273",
00543   "hrw100","hrw110",
00544   "ici382","ili334",
00545   "ili331","ili238",
00546   "ili331","ili274",
00547   "ili362","ili363",
00548   "ili381","ili281",
00549   "ili381","mat210",
00550   "iln230","iwn170",
00551   "ici313","ili331",
00552   "ici332","ici393",
00553   "ici332","ili331",
00554   "ici344","ili243",
00555   "icn336","ici393",
00556   "ici314","ici313",
00557   0,0
00558   };
00559 
00561   const Curriculum curriculum[]=
00562     { { 8, 10, 24, 2, 10,
00563         courses8, prereqs8
00564       },
00565       { 10, 10, 24, 2, 10,
00566         courses10, prereqs10
00567       },
00568       { 12, 10, 24, 2, 10,
00569         courses12, prereqs12
00570       }
00571     };
00572 
00574   const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
00575 
00577 }
00578 
00579 // STATISTICS: example-any
00580