Generated on Tue Jul 27 2010 21:59:08 for Gecode by doxygen 1.7.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: 2010-05-08 13:09:21 +0200 (Sat, 08 May 2010) $ by $Author: tack $
00015  *     $Revision: 10907 $
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 MinimizeScript {
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     int p = curr.p;
00125     int a = curr.a;
00126     int b = curr.b;
00127     int c = curr.c;
00128     int d = curr.d;
00129 
00130     std::map<std::string, int> courseMap; // Map names to course numbers
00131     int maxCredit = 0;
00132     int numberOfCourses = 0;
00133     for (const Course* c=curr.courses; c->name != 0; c++) {
00134       courseMap[c->name] = numberOfCourses++;
00135       maxCredit += c->credit;
00136     }
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 
00161     // Optimization criterion: minimize u
00162     max(*this, l, u);
00163 
00164     // Redundant constraints
00165     linear(*this, l, IRT_EQ, maxCredit);
00166     linear(*this, q, IRT_EQ, numberOfCourses);
00167 
00168     if (opt.branching() == BRANCHING_NAIVE) {
00169       branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00170     } else {
00171       Int::Branch::BySizeMin varsel(*this, VarBranchOptions::def);
00172       ViewArray<Int::IntView> xv(*this, IntVarArgs(x));
00173       if (opt.branching() == BRANCHING_LOAD) {
00174         ValBestLoad<true> valsel(*this, ValBranchOptions::def);
00175         ViewValBrancher<Int::Branch::BySizeMin, ValBestLoad<true> >
00176           ::post(*this,xv,varsel,valsel);
00177       } else { 
00178         ValBestLoad<false> valsel(*this, ValBranchOptions::def);
00179         ViewValBrancher<Int::Branch::BySizeMin, ValBestLoad<false> >
00180           ::post(*this,xv,varsel,valsel);
00181       }
00182     }
00183   }
00184     
00186   BACP(bool share, BACP& bacp) : MinimizeScript(share,bacp),
00187     curr(bacp.curr) {
00188     l.update(*this, share, bacp.l);
00189     u.update(*this, share, bacp.u);
00190     x.update(*this, share, bacp.x);
00191   }
00193   virtual Space*
00194   copy(bool share) {
00195     return new BACP(share,*this);
00196   }
00198   virtual IntVar cost(void) const {
00199     return u;
00200   }
00202   virtual void
00203   print(std::ostream& os) const {
00204     std::vector<std::list<int> > period(curr.p);
00205     for (int i=x.size(); i--;)
00206       period[x[i].val()].push_back(i);
00207 
00208     os << "Solution with load " << u.val() << ":" << std::endl;
00209     for (int i=0; i<curr.p; i++) {
00210       os << "\tPeriod "<<i+1<<": ";
00211       for (std::list<int>::iterator v=period[i].begin();
00212            v != period[i].end(); ++v) {
00213         os << curr.courses[*v].name << " ";
00214       }
00215       os << std::endl;
00216     }
00217     os << std::endl;
00218   }
00219 
00226   template <bool minimize>
00227   class ValBestLoad : public ValSelBase<Int::IntView,int> {
00228   public:
00230     ValBestLoad(void) {}
00231 
00233     ValBestLoad(Space& home, const ValBranchOptions& vbo)
00234       : ValSelBase<Int::IntView,int>(home,vbo) {}
00235 
00237     int val(Space& home, Int::IntView x) const {
00238       BACP& b = static_cast<BACP&>(home);
00239       Int::ViewValues<Int::IntView> values(x);
00240       int val = -1;
00241       int best = minimize ? Int::Limits::max+1 : Int::Limits::min-1;
00242       while (values()) {
00243         if (minimize 
00244             ? b.l[values.val()].min() < best
00245             : b.l[values.val()].min() > best) {
00246           val  = values.val();
00247           best = b.l[val].min();
00248         }
00249         ++values;
00250       }
00251       assert(val != -1);
00252       return val;
00253     }
00254 
00256     ModEvent tell(Space& home, unsigned int a, Int::IntView x, int n) {
00257       return (a == 0) ? x.eq(home,n) : x.gr(home,n);
00258     }
00259   };
00260 };
00261 
00265 int
00266 main(int argc, char* argv[]) {
00267   SizeOptions opt("BACP");
00268   opt.branching(BACP::BRANCHING_NAIVE);
00269   opt.branching(BACP::BRANCHING_NAIVE,"naive");
00270   opt.branching(BACP::BRANCHING_LOAD,"load");
00271   opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
00272   opt.size(2);
00273   opt.solutions(0);
00274   opt.iterations(20);
00275   opt.parse(argc,argv);
00276   if (opt.size() >= n_examples) {
00277     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00278               << std::endl;
00279     return 1;
00280   }
00281   MinimizeScript::run<BACP,BAB,SizeOptions>(opt);
00282   return 0;
00283 }
00284 
00285 namespace {
00291 
00292   const Course courses8[] =
00293     {
00294       {"dew100", 1},
00295       {"fis100", 3},
00296       {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
00297       {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
00298       {"iei134", 3},{"iei141", 3},{"mat194", 4},
00299       {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
00300       {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
00301       {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
00302       {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
00303       {0,0}
00304     };
00305 
00307   const char* prereqs8[] =
00308     {
00309     "dew101","dew100",
00310     "fis101","fis100",
00311     "fis101","mat192",
00312     "mat191","mat190",
00313     "mat193","mat190",
00314     "mat193","mat192",
00315     "fis102","fis101",
00316     "fis102","mat193",
00317     "iei134","iwi131",
00318     "iei141","iwi131",
00319     "mat194","mat191 ",
00320     "mat194","mat193",
00321     "dewxx0","dew101",
00322     "hcw311","hcw310",
00323     "iei132","iei134",
00324     "iei133","iei134",
00325     "iei142","iei141",
00326     "mat195","mat194",
00327     "iei231","iei134",
00328     "iei241","iei142",
00329     "iei271","iei162",
00330     "iei281","mat195",
00331     "iei233","iei231",
00332     "iei238","iei231",
00333     "iei261","iwn261",
00334     "iei272","iei271",
00335     "iei273","iei271",
00336     "iei273","iei271",
00337     "iei161","iwn261",
00338     "iei161","iwn261",
00339     "iei232","iei273",
00340     "iei232","iei273",
00341     "iei262","iwn261",
00342     "iei274","iei273",
00343     "iei274","iei273",
00344     "iei219","iei232",
00345     "iei248","iei233",
00346     "iei248","iei233",
00347     0,0
00348     };
00349 
00351   const Course courses10[] = {
00352   {"dew100",1},
00353   {"fis100",3},
00354   {"hrwxx1",2},
00355   {"iwg101",2},
00356   {"mat021",5},
00357   {"qui010",3},
00358   {"dew101",1},
00359   {"fis110",5},
00360   {"hrwxx2",2},
00361   {"iwi131",3},
00362   {"mat022",5},
00363   {"dewxx0",1},
00364   {"fis120",4},
00365   {"hcw310",1},
00366   {"hrwxx3",2},
00367   {"ili134",4},
00368   {"ili151",3},
00369   {"mat023",4},
00370   {"hcw311",1},
00371   {"ili135",4},
00372   {"ili153",3},
00373   {"ili260",3},
00374   {"iwn261",3},
00375   {"mat024",4},
00376   {"fis130",4},
00377   {"ili239",4},
00378   {"ili245",4},
00379   {"ili253",4},
00380   {"fis140",4},
00381   {"ili236",4},
00382   {"ili243",4},
00383   {"ili270",3},
00384   {"ili280",4},
00385   {"ici344",4},
00386   {"ili263",3},
00387   {"ili332",4},
00388   {"ili355",4},
00389   {"iwn170",3},
00390   {"icdxx1",3},
00391   {"ili362",3},
00392   {"iwn270",3},
00393   {"icdxx2",3},
00394   {0,0}
00395   };
00396 
00398   const char* prereqs10[] = {
00399   "dew101","dew100",
00400   "fis110","fis100",
00401   "fis110","mat021",
00402   "mat022","mat021",
00403   "dewxx0","dew101",
00404   "fis120","fis110",
00405   "fis120","mat022",
00406   "ili134","iwi131",
00407   "ili151","iwi131",
00408   "mat023","mat022",
00409   "hcw311","hcw310",
00410   "ili135","ili134",
00411   "ili153","ili134",
00412   "ili153","ili151",
00413   "mat024","mat023",
00414   "fis130","fis110",
00415   "fis130","mat022",
00416   "ili239","ili135",
00417   "ili245","ili153",
00418   "ili253","ili153",
00419   "fis140","fis120",
00420   "fis140","fis130",
00421   "ili236","ili239",
00422   "ili243","ili245",
00423   "ili270","ili260",
00424   "ili270","iwn261",
00425   "ili280","mat024",
00426   "ici344","ili243",
00427   "ili263","ili260",
00428   "ili263","iwn261",
00429   "ili332","ili236",
00430   "ili355","ili153",
00431   "ili355","ili280",
00432   "ili362","ili263",
00433   0,0
00434   };
00435 
00437   const Course courses12[] = {
00438   {"dew100",1},
00439   {"fis100",3},
00440   {"hcw310",1},
00441   {"iwg101",2},
00442   {"mat111",4},
00443   {"mat121",4},
00444   {"dew101",1},
00445   {"fis110",5},
00446   {"iwi131",3},
00447   {"mat112",4},
00448   {"mat122",4},
00449   {"dewxx0",1},
00450   {"fis120",4},
00451   {"hcw311",1},
00452   {"hxwxx1",1},
00453   {"ili142",4},
00454   {"mat113",4},
00455   {"mat123",4},
00456   {"fis130",4},
00457   {"ili134",4},
00458   {"ili151",3},
00459   {"iwm185",3},
00460   {"mat124",4},
00461   {"fis140",4},
00462   {"hxwxx2",1},
00463   {"ile260",3},
00464   {"ili260",3},
00465   {"iwn170",3},
00466   {"qui104",3},
00467   {"ili231",3},
00468   {"ili243",4},
00469   {"ili252",4},
00470   {"ili273",3},
00471   {"mat210",4},
00472   {"mat260",4},
00473   {"ild208",3},
00474   {"ili221",4},
00475   {"ili274",3},
00476   {"ili281",3},
00477   {"iwn270",3},
00478   {"mat270",4},
00479   {"hrw150",2},
00480   {"ili238",4},
00481   {"ili242",3},
00482   {"ili275",3},
00483   {"ili355",4},
00484   {"hrw110",2},
00485   {"ici393",4},
00486   {"ili237",4},
00487   {"ili334",4},
00488   {"ili363",3},
00489   {"iwn261",3},
00490   {"hrw100",2},
00491   {"ici382",4},
00492   {"ili331",4},
00493   {"ili362",3},
00494   {"ili381",3},
00495   {"iln230",3},
00496   {"ici313",2},
00497   {"ici315",2},
00498   {"ici332",3},
00499   {"ici344",4},
00500   {"icn336",3},
00501   {"iwi365",3},
00502   {"ici314",2},
00503   {"ici367",2},
00504   {0,0}
00505   };
00506 
00508   const char* prereqs12[] = {
00509   "dew101","dew100",
00510   "fis110","fis100",
00511   "fis110","mat121",
00512   "mat112","mat111",
00513   "mat122","mat111",
00514   "mat122","mat121",
00515   "dewxx0","dew101",
00516   "fis120","fis110",
00517   "fis120","mat122",
00518   "hcw311","hcw310",
00519   "ili142","iwi131",
00520   "mat113","mat112",
00521   "mat113","mat122",
00522   "mat123","mat112",
00523   "mat123","mat122",
00524   "fis130","fis110",
00525   "fis130","mat122",
00526   "ili134","iwi131",
00527   "ili151","mat112",
00528   "mat124","mat113",
00529   "mat124","mat123",
00530   "fis140","fis120",
00531   "fis140","fis130",
00532   "ile260","fis120",
00533   "ile260","mat124",
00534   "ili231","iwi131",
00535   "ili252","iwi131",
00536   "ili273","ili260",
00537   "mat210","mat113",
00538   "mat260","iwi131",
00539   "mat260","mat113",
00540   "mat260","mat123",
00541   "ili221","ili134",
00542   "ili221","ili231",
00543   "ili221","mat260",
00544   "ili274","ili273",
00545   "ili281","mat260",
00546   "mat270","iwi131",
00547   "mat270","mat113",
00548   "mat270","mat123",
00549   "ili238","ili134",
00550   "ili242","ili142",
00551   "ili275","ili274",
00552   "ili355","ili221",
00553   "hrw110","hrw150",
00554   "ici393","mat210",
00555   "ici393","mat260",
00556   "ili237","ili231",
00557   "ili237","ili252",
00558   "ili334","ili238",
00559   "ili363","ili273",
00560   "hrw100","hrw110",
00561   "ici382","ili334",
00562   "ili331","ili238",
00563   "ili331","ili274",
00564   "ili362","ili363",
00565   "ili381","ili281",
00566   "ili381","mat210",
00567   "iln230","iwn170",
00568   "ici313","ili331",
00569   "ici332","ici393",
00570   "ici332","ili331",
00571   "ici344","ili243",
00572   "icn336","ici393",
00573   "ici314","ici313",
00574   0,0
00575   };
00576 
00578   const Curriculum curriculum[]=
00579     { { 8, 10, 24, 2, 10,
00580         courses8, prereqs8
00581       },
00582       { 10, 10, 24, 2, 10,
00583         courses10, prereqs10
00584       },
00585       { 12, 10, 24, 2, 10,
00586         courses12, prereqs12
00587       }
00588     };
00589 
00591   const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
00592 
00594 }
00595 
00596 // STATISTICS: example-any
00597