Generated on Wed Nov 5 2014 05:18:15 for Gecode by doxygen 1.7.6.1
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  *  Last modified:
00014  *     $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
00015  *     $Revision: 13820 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #include <gecode/driver.hh>
00043 #include <gecode/int.hh>
00044 #include <gecode/minimodel.hh>
00045 #include <gecode/int/branch.hh>
00046 
00047 #include <map>
00048 #include <string>
00049 #include <list>
00050 #include <vector>
00051 
00052 using namespace Gecode;
00053 
00055 class Course {
00056 public:
00057   const char* name; 
00058   int credit;       
00059 };
00060 
00062 class Curriculum {
00063 public:
00065   int p;
00067   int a;
00069   int b;
00071   int c;
00073   int d;
00074 
00076   const Course *courses;
00078   const char **prereqs;
00079 };
00080 
00081 namespace {
00082 
00083   extern const Curriculum curriculum[];
00084   extern const unsigned int n_examples;
00085 
00086 }
00087 
00100 class BACP : public IntMinimizeScript {
00101 protected:
00103   const Curriculum curr;
00104 
00106   IntVarArray l;
00108   IntVar u;
00110   IntVarArray q;
00111 
00113   IntVarArray x;
00114 public:
00116   enum {
00117     BRANCHING_NAIVE,    
00118     BRANCHING_LOAD,     
00119     BRANCHING_LOAD_REV, 
00120   };
00121 
00123   BACP(const SizeOptions& opt) : curr(curriculum[opt.size()]) {
00124     std::map<std::string, int> courseMap; // Map names to course numbers
00125     int maxCredit = 0;
00126     int numberOfCourses = 0;
00127     for (const Course* co=curr.courses; co->name != 0; co++) {
00128       courseMap[co->name] = numberOfCourses++;
00129       maxCredit += co->credit;
00130     }
00131 
00132     int p = curr.p;
00133     int a = curr.a;
00134     int b = curr.b;
00135     int c = curr.c;
00136     int d = curr.d;
00137 
00138     l = IntVarArray(*this, p, a, b);
00139     u = IntVar(*this, 0, maxCredit);
00140     q = IntVarArray(*this, p, c, d);
00141     x = IntVarArray(*this, numberOfCourses, 0, p-1);
00142 
00143     for (int j=0; j<p; j++) {
00144       BoolVarArgs xij(*this, numberOfCourses, 0, 1);
00145       IntArgs t(numberOfCourses);
00146       for (int i=0; i<numberOfCourses; i++) {
00147         rel(*this, (x[i]==j) == xij[i]);
00148         t[i] = curr.courses[i].credit;
00149       }
00150       // sum over all t*(xi==j) is load of period i
00151       linear(*this, t, xij, IRT_EQ, l[j]);
00152       // sum over all (xi==j) is number of courses in period i
00153       linear(*this, xij, IRT_EQ, q[j]);
00154     }
00155 
00156     // Precedence
00157     for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
00158       rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
00159 
00160     // Optimization criterion: minimize u
00161     max(*this, l, u);
00162 
00163     // Redundant constraints
00164     linear(*this, l, IRT_EQ, maxCredit);
00165     linear(*this, q, IRT_EQ, numberOfCourses);
00166 
00167     switch (opt.branching()) {
00168     case BRANCHING_NAIVE:
00169       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00170       break;
00171     case BRANCHING_LOAD:
00172       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load));
00173       break;
00174     case BRANCHING_LOAD_REV:
00175       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load_rev));
00176       break;
00177     }
00178   }
00180   static int load(const Space& home, IntVar x, int) {
00181     const BACP& b = static_cast<const BACP&>(home);
00182     IntVarValues values(x);
00183     int val = -1;
00184     int best = Int::Limits::max+1;
00185     while (values()) {
00186       if (b.l[values.val()].min() < best) {
00187         val  = values.val();
00188         best = b.l[val].min();
00189       }
00190       ++values;
00191     }
00192     assert(val != -1);
00193     return val;
00194   }
00196   static int load_rev(const Space& home, IntVar x, int) {
00197     const BACP& b = static_cast<const BACP&>(home);
00198     IntVarValues values(x);
00199     int val = -1;
00200     int best = Int::Limits::min-1;
00201     while (values()) {
00202       if (b.l[values.val()].min() > best) {
00203         val  = values.val();
00204         best = b.l[val].min();
00205       }
00206       ++values;
00207     }
00208     assert(val != -1);
00209     return val;
00210   }
00212   BACP(bool share, BACP& bacp) : IntMinimizeScript(share,bacp),
00213     curr(bacp.curr) {
00214     l.update(*this, share, bacp.l);
00215     u.update(*this, share, bacp.u);
00216     x.update(*this, share, bacp.x);
00217   }
00219   virtual Space*
00220   copy(bool share) {
00221     return new BACP(share,*this);
00222   }
00224   virtual IntVar cost(void) const {
00225     return u;
00226   }
00228   virtual void
00229   print(std::ostream& os) const {
00230     std::vector<std::list<int> > period(curr.p);
00231     for (int i=x.size(); i--;)
00232       period[x[i].val()].push_back(i);
00233 
00234     os << "Solution with load " << u.val() << ":" << std::endl;
00235     for (int i=0; i<curr.p; i++) {
00236       os << "\tPeriod "<<i+1<<": ";
00237       for (std::list<int>::iterator v=period[i].begin();
00238            v != period[i].end(); ++v) {
00239         os << curr.courses[*v].name << " ";
00240       }
00241       os << std::endl;
00242     }
00243     os << std::endl;
00244   }
00245 
00246 };
00247 
00251 int
00252 main(int argc, char* argv[]) {
00253   SizeOptions opt("BACP");
00254   opt.branching(BACP::BRANCHING_NAIVE);
00255   opt.branching(BACP::BRANCHING_NAIVE,"naive");
00256   opt.branching(BACP::BRANCHING_LOAD,"load");
00257   opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
00258   opt.size(2);
00259   opt.solutions(0);
00260   opt.iterations(20);
00261   opt.parse(argc,argv);
00262   if (opt.size() >= n_examples) {
00263     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00264               << std::endl;
00265     return 1;
00266   }
00267   IntMinimizeScript::run<BACP,BAB,SizeOptions>(opt);
00268   return 0;
00269 }
00270 
00271 namespace {
00277 
00278   const Course courses8[] =
00279     {
00280       {"dew100", 1},
00281       {"fis100", 3},
00282       {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
00283       {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
00284       {"iei134", 3},{"iei141", 3},{"mat194", 4},
00285       {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
00286       {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
00287       {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
00288       {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
00289       {0,0}
00290     };
00291 
00293   const char* prereqs8[] =
00294     {
00295     "dew101","dew100",
00296     "fis101","fis100",
00297     "fis101","mat192",
00298     "mat191","mat190",
00299     "mat193","mat190",
00300     "mat193","mat192",
00301     "fis102","fis101",
00302     "fis102","mat193",
00303     "iei134","iwi131",
00304     "iei141","iwi131",
00305     "mat194","mat191 ",
00306     "mat194","mat193",
00307     "dewxx0","dew101",
00308     "hcw311","hcw310",
00309     "iei132","iei134",
00310     "iei133","iei134",
00311     "iei142","iei141",
00312     "mat195","mat194",
00313     "iei231","iei134",
00314     "iei241","iei142",
00315     "iei271","iei162",
00316     "iei281","mat195",
00317     "iei233","iei231",
00318     "iei238","iei231",
00319     "iei261","iwn261",
00320     "iei272","iei271",
00321     "iei273","iei271",
00322     "iei273","iei271",
00323     "iei161","iwn261",
00324     "iei161","iwn261",
00325     "iei232","iei273",
00326     "iei232","iei273",
00327     "iei262","iwn261",
00328     "iei274","iei273",
00329     "iei274","iei273",
00330     "iei219","iei232",
00331     "iei248","iei233",
00332     "iei248","iei233",
00333     0,0
00334     };
00335 
00337   const Course courses10[] = {
00338   {"dew100",1},
00339   {"fis100",3},
00340   {"hrwxx1",2},
00341   {"iwg101",2},
00342   {"mat021",5},
00343   {"qui010",3},
00344   {"dew101",1},
00345   {"fis110",5},
00346   {"hrwxx2",2},
00347   {"iwi131",3},
00348   {"mat022",5},
00349   {"dewxx0",1},
00350   {"fis120",4},
00351   {"hcw310",1},
00352   {"hrwxx3",2},
00353   {"ili134",4},
00354   {"ili151",3},
00355   {"mat023",4},
00356   {"hcw311",1},
00357   {"ili135",4},
00358   {"ili153",3},
00359   {"ili260",3},
00360   {"iwn261",3},
00361   {"mat024",4},
00362   {"fis130",4},
00363   {"ili239",4},
00364   {"ili245",4},
00365   {"ili253",4},
00366   {"fis140",4},
00367   {"ili236",4},
00368   {"ili243",4},
00369   {"ili270",3},
00370   {"ili280",4},
00371   {"ici344",4},
00372   {"ili263",3},
00373   {"ili332",4},
00374   {"ili355",4},
00375   {"iwn170",3},
00376   {"icdxx1",3},
00377   {"ili362",3},
00378   {"iwn270",3},
00379   {"icdxx2",3},
00380   {0,0}
00381   };
00382 
00384   const char* prereqs10[] = {
00385   "dew101","dew100",
00386   "fis110","fis100",
00387   "fis110","mat021",
00388   "mat022","mat021",
00389   "dewxx0","dew101",
00390   "fis120","fis110",
00391   "fis120","mat022",
00392   "ili134","iwi131",
00393   "ili151","iwi131",
00394   "mat023","mat022",
00395   "hcw311","hcw310",
00396   "ili135","ili134",
00397   "ili153","ili134",
00398   "ili153","ili151",
00399   "mat024","mat023",
00400   "fis130","fis110",
00401   "fis130","mat022",
00402   "ili239","ili135",
00403   "ili245","ili153",
00404   "ili253","ili153",
00405   "fis140","fis120",
00406   "fis140","fis130",
00407   "ili236","ili239",
00408   "ili243","ili245",
00409   "ili270","ili260",
00410   "ili270","iwn261",
00411   "ili280","mat024",
00412   "ici344","ili243",
00413   "ili263","ili260",
00414   "ili263","iwn261",
00415   "ili332","ili236",
00416   "ili355","ili153",
00417   "ili355","ili280",
00418   "ili362","ili263",
00419   0,0
00420   };
00421 
00423   const Course courses12[] = {
00424   {"dew100",1},
00425   {"fis100",3},
00426   {"hcw310",1},
00427   {"iwg101",2},
00428   {"mat111",4},
00429   {"mat121",4},
00430   {"dew101",1},
00431   {"fis110",5},
00432   {"iwi131",3},
00433   {"mat112",4},
00434   {"mat122",4},
00435   {"dewxx0",1},
00436   {"fis120",4},
00437   {"hcw311",1},
00438   {"hxwxx1",1},
00439   {"ili142",4},
00440   {"mat113",4},
00441   {"mat123",4},
00442   {"fis130",4},
00443   {"ili134",4},
00444   {"ili151",3},
00445   {"iwm185",3},
00446   {"mat124",4},
00447   {"fis140",4},
00448   {"hxwxx2",1},
00449   {"ile260",3},
00450   {"ili260",3},
00451   {"iwn170",3},
00452   {"qui104",3},
00453   {"ili231",3},
00454   {"ili243",4},
00455   {"ili252",4},
00456   {"ili273",3},
00457   {"mat210",4},
00458   {"mat260",4},
00459   {"ild208",3},
00460   {"ili221",4},
00461   {"ili274",3},
00462   {"ili281",3},
00463   {"iwn270",3},
00464   {"mat270",4},
00465   {"hrw150",2},
00466   {"ili238",4},
00467   {"ili242",3},
00468   {"ili275",3},
00469   {"ili355",4},
00470   {"hrw110",2},
00471   {"ici393",4},
00472   {"ili237",4},
00473   {"ili334",4},
00474   {"ili363",3},
00475   {"iwn261",3},
00476   {"hrw100",2},
00477   {"ici382",4},
00478   {"ili331",4},
00479   {"ili362",3},
00480   {"ili381",3},
00481   {"iln230",3},
00482   {"ici313",2},
00483   {"ici315",2},
00484   {"ici332",3},
00485   {"ici344",4},
00486   {"icn336",3},
00487   {"iwi365",3},
00488   {"ici314",2},
00489   {"ici367",2},
00490   {0,0}
00491   };
00492 
00494   const char* prereqs12[] = {
00495   "dew101","dew100",
00496   "fis110","fis100",
00497   "fis110","mat121",
00498   "mat112","mat111",
00499   "mat122","mat111",
00500   "mat122","mat121",
00501   "dewxx0","dew101",
00502   "fis120","fis110",
00503   "fis120","mat122",
00504   "hcw311","hcw310",
00505   "ili142","iwi131",
00506   "mat113","mat112",
00507   "mat113","mat122",
00508   "mat123","mat112",
00509   "mat123","mat122",
00510   "fis130","fis110",
00511   "fis130","mat122",
00512   "ili134","iwi131",
00513   "ili151","mat112",
00514   "mat124","mat113",
00515   "mat124","mat123",
00516   "fis140","fis120",
00517   "fis140","fis130",
00518   "ile260","fis120",
00519   "ile260","mat124",
00520   "ili231","iwi131",
00521   "ili252","iwi131",
00522   "ili273","ili260",
00523   "mat210","mat113",
00524   "mat260","iwi131",
00525   "mat260","mat113",
00526   "mat260","mat123",
00527   "ili221","ili134",
00528   "ili221","ili231",
00529   "ili221","mat260",
00530   "ili274","ili273",
00531   "ili281","mat260",
00532   "mat270","iwi131",
00533   "mat270","mat113",
00534   "mat270","mat123",
00535   "ili238","ili134",
00536   "ili242","ili142",
00537   "ili275","ili274",
00538   "ili355","ili221",
00539   "hrw110","hrw150",
00540   "ici393","mat210",
00541   "ici393","mat260",
00542   "ili237","ili231",
00543   "ili237","ili252",
00544   "ili334","ili238",
00545   "ili363","ili273",
00546   "hrw100","hrw110",
00547   "ici382","ili334",
00548   "ili331","ili238",
00549   "ili331","ili274",
00550   "ili362","ili363",
00551   "ili381","ili281",
00552   "ili381","mat210",
00553   "iln230","iwn170",
00554   "ici313","ili331",
00555   "ici332","ici393",
00556   "ici332","ili331",
00557   "ici344","ili243",
00558   "icn336","ici393",
00559   "ici314","ici313",
00560   0,0
00561   };
00562 
00564   const Curriculum curriculum[]=
00565     { { 8, 10, 24, 2, 10,
00566         courses8, prereqs8
00567       },
00568       { 10, 10, 24, 2, 10,
00569         courses10, prereqs10
00570       },
00571       { 12, 10, 24, 2, 10,
00572         courses12, prereqs12
00573       }
00574     };
00575 
00577   const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
00578 
00580 }
00581 
00582 // STATISTICS: example-any
00583