00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
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)
00124 : IntMinimizeScript(opt), curr(curriculum[opt.size()]) {
00125 std::map<std::string, int> courseMap;
00126 int maxCredit = 0;
00127 int numberOfCourses = 0;
00128 for (const Course* co=curr.courses; co->name != 0; co++) {
00129 courseMap[co->name] = numberOfCourses++;
00130 maxCredit += co->credit;
00131 }
00132
00133 int p = curr.p;
00134 int a = curr.a;
00135 int b = curr.b;
00136 int c = curr.c;
00137 int d = curr.d;
00138
00139 l = IntVarArray(*this, p, a, b);
00140 u = IntVar(*this, 0, maxCredit);
00141 q = IntVarArray(*this, p, c, d);
00142 x = IntVarArray(*this, numberOfCourses, 0, p-1);
00143
00144 for (int j=0; j<p; j++) {
00145 BoolVarArgs xij(*this, numberOfCourses, 0, 1);
00146 IntArgs t(numberOfCourses);
00147 for (int i=0; i<numberOfCourses; i++) {
00148 rel(*this, (x[i]==j) == xij[i]);
00149 t[i] = curr.courses[i].credit;
00150 }
00151
00152 linear(*this, t, xij, IRT_EQ, l[j]);
00153
00154 linear(*this, xij, IRT_EQ, q[j]);
00155 }
00156
00157
00158 for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
00159 rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
00160
00161
00162 max(*this, l, u);
00163
00164
00165 linear(*this, l, IRT_EQ, maxCredit);
00166 linear(*this, q, IRT_EQ, numberOfCourses);
00167
00168 switch (opt.branching()) {
00169 case BRANCHING_NAIVE:
00170 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00171 break;
00172 case BRANCHING_LOAD:
00173 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load));
00174 break;
00175 case BRANCHING_LOAD_REV:
00176 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load_rev));
00177 break;
00178 }
00179 }
00181 static int load(const Space& home, IntVar x, int) {
00182 const BACP& b = static_cast<const BACP&>(home);
00183 IntVarValues values(x);
00184 int val = -1;
00185 int best = Int::Limits::max+1;
00186 while (values()) {
00187 if (b.l[values.val()].min() < best) {
00188 val = values.val();
00189 best = b.l[val].min();
00190 }
00191 ++values;
00192 }
00193 assert(val != -1);
00194 return val;
00195 }
00197 static int load_rev(const Space& home, IntVar x, int) {
00198 const BACP& b = static_cast<const BACP&>(home);
00199 IntVarValues values(x);
00200 int val = -1;
00201 int best = Int::Limits::min-1;
00202 while (values()) {
00203 if (b.l[values.val()].min() > best) {
00204 val = values.val();
00205 best = b.l[val].min();
00206 }
00207 ++values;
00208 }
00209 assert(val != -1);
00210 return val;
00211 }
00213 BACP(bool share, BACP& bacp) : IntMinimizeScript(share,bacp),
00214 curr(bacp.curr) {
00215 l.update(*this, share, bacp.l);
00216 u.update(*this, share, bacp.u);
00217 x.update(*this, share, bacp.x);
00218 }
00220 virtual Space*
00221 copy(bool share) {
00222 return new BACP(share,*this);
00223 }
00225 virtual IntVar cost(void) const {
00226 return u;
00227 }
00229 virtual void
00230 print(std::ostream& os) const {
00231 std::vector<std::list<int> > period(curr.p);
00232 for (int i=x.size(); i--;)
00233 period[x[i].val()].push_back(i);
00234
00235 os << "Solution with load " << u.val() << ":" << std::endl;
00236 for (int i=0; i<curr.p; i++) {
00237 os << "\tPeriod "<<i+1<<": ";
00238 for (std::list<int>::iterator v=period[i].begin();
00239 v != period[i].end(); ++v) {
00240 os << curr.courses[*v].name << " ";
00241 }
00242 os << std::endl;
00243 }
00244 os << std::endl;
00245 }
00246
00247 };
00248
00252 int
00253 main(int argc, char* argv[]) {
00254 SizeOptions opt("BACP");
00255 opt.branching(BACP::BRANCHING_NAIVE);
00256 opt.branching(BACP::BRANCHING_NAIVE,"naive");
00257 opt.branching(BACP::BRANCHING_LOAD,"load");
00258 opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
00259 opt.size(2);
00260 opt.solutions(0);
00261 opt.iterations(20);
00262 opt.parse(argc,argv);
00263 if (opt.size() >= n_examples) {
00264 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00265 << std::endl;
00266 return 1;
00267 }
00268 IntMinimizeScript::run<BACP,BAB,SizeOptions>(opt);
00269 return 0;
00270 }
00271
00272 namespace {
00278
00279 const Course courses8[] =
00280 {
00281 {"dew100", 1},
00282 {"fis100", 3},
00283 {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
00284 {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
00285 {"iei134", 3},{"iei141", 3},{"mat194", 4},
00286 {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
00287 {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
00288 {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
00289 {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
00290 {0,0}
00291 };
00292
00294 const char* prereqs8[] =
00295 {
00296 "dew101","dew100",
00297 "fis101","fis100",
00298 "fis101","mat192",
00299 "mat191","mat190",
00300 "mat193","mat190",
00301 "mat193","mat192",
00302 "fis102","fis101",
00303 "fis102","mat193",
00304 "iei134","iwi131",
00305 "iei141","iwi131",
00306 "mat194","mat191 ",
00307 "mat194","mat193",
00308 "dewxx0","dew101",
00309 "hcw311","hcw310",
00310 "iei132","iei134",
00311 "iei133","iei134",
00312 "iei142","iei141",
00313 "mat195","mat194",
00314 "iei231","iei134",
00315 "iei241","iei142",
00316 "iei271","iei162",
00317 "iei281","mat195",
00318 "iei233","iei231",
00319 "iei238","iei231",
00320 "iei261","iwn261",
00321 "iei272","iei271",
00322 "iei273","iei271",
00323 "iei273","iei271",
00324 "iei161","iwn261",
00325 "iei161","iwn261",
00326 "iei232","iei273",
00327 "iei232","iei273",
00328 "iei262","iwn261",
00329 "iei274","iei273",
00330 "iei274","iei273",
00331 "iei219","iei232",
00332 "iei248","iei233",
00333 "iei248","iei233",
00334 0,0
00335 };
00336
00338 const Course courses10[] = {
00339 {"dew100",1},
00340 {"fis100",3},
00341 {"hrwxx1",2},
00342 {"iwg101",2},
00343 {"mat021",5},
00344 {"qui010",3},
00345 {"dew101",1},
00346 {"fis110",5},
00347 {"hrwxx2",2},
00348 {"iwi131",3},
00349 {"mat022",5},
00350 {"dewxx0",1},
00351 {"fis120",4},
00352 {"hcw310",1},
00353 {"hrwxx3",2},
00354 {"ili134",4},
00355 {"ili151",3},
00356 {"mat023",4},
00357 {"hcw311",1},
00358 {"ili135",4},
00359 {"ili153",3},
00360 {"ili260",3},
00361 {"iwn261",3},
00362 {"mat024",4},
00363 {"fis130",4},
00364 {"ili239",4},
00365 {"ili245",4},
00366 {"ili253",4},
00367 {"fis140",4},
00368 {"ili236",4},
00369 {"ili243",4},
00370 {"ili270",3},
00371 {"ili280",4},
00372 {"ici344",4},
00373 {"ili263",3},
00374 {"ili332",4},
00375 {"ili355",4},
00376 {"iwn170",3},
00377 {"icdxx1",3},
00378 {"ili362",3},
00379 {"iwn270",3},
00380 {"icdxx2",3},
00381 {0,0}
00382 };
00383
00385 const char* prereqs10[] = {
00386 "dew101","dew100",
00387 "fis110","fis100",
00388 "fis110","mat021",
00389 "mat022","mat021",
00390 "dewxx0","dew101",
00391 "fis120","fis110",
00392 "fis120","mat022",
00393 "ili134","iwi131",
00394 "ili151","iwi131",
00395 "mat023","mat022",
00396 "hcw311","hcw310",
00397 "ili135","ili134",
00398 "ili153","ili134",
00399 "ili153","ili151",
00400 "mat024","mat023",
00401 "fis130","fis110",
00402 "fis130","mat022",
00403 "ili239","ili135",
00404 "ili245","ili153",
00405 "ili253","ili153",
00406 "fis140","fis120",
00407 "fis140","fis130",
00408 "ili236","ili239",
00409 "ili243","ili245",
00410 "ili270","ili260",
00411 "ili270","iwn261",
00412 "ili280","mat024",
00413 "ici344","ili243",
00414 "ili263","ili260",
00415 "ili263","iwn261",
00416 "ili332","ili236",
00417 "ili355","ili153",
00418 "ili355","ili280",
00419 "ili362","ili263",
00420 0,0
00421 };
00422
00424 const Course courses12[] = {
00425 {"dew100",1},
00426 {"fis100",3},
00427 {"hcw310",1},
00428 {"iwg101",2},
00429 {"mat111",4},
00430 {"mat121",4},
00431 {"dew101",1},
00432 {"fis110",5},
00433 {"iwi131",3},
00434 {"mat112",4},
00435 {"mat122",4},
00436 {"dewxx0",1},
00437 {"fis120",4},
00438 {"hcw311",1},
00439 {"hxwxx1",1},
00440 {"ili142",4},
00441 {"mat113",4},
00442 {"mat123",4},
00443 {"fis130",4},
00444 {"ili134",4},
00445 {"ili151",3},
00446 {"iwm185",3},
00447 {"mat124",4},
00448 {"fis140",4},
00449 {"hxwxx2",1},
00450 {"ile260",3},
00451 {"ili260",3},
00452 {"iwn170",3},
00453 {"qui104",3},
00454 {"ili231",3},
00455 {"ili243",4},
00456 {"ili252",4},
00457 {"ili273",3},
00458 {"mat210",4},
00459 {"mat260",4},
00460 {"ild208",3},
00461 {"ili221",4},
00462 {"ili274",3},
00463 {"ili281",3},
00464 {"iwn270",3},
00465 {"mat270",4},
00466 {"hrw150",2},
00467 {"ili238",4},
00468 {"ili242",3},
00469 {"ili275",3},
00470 {"ili355",4},
00471 {"hrw110",2},
00472 {"ici393",4},
00473 {"ili237",4},
00474 {"ili334",4},
00475 {"ili363",3},
00476 {"iwn261",3},
00477 {"hrw100",2},
00478 {"ici382",4},
00479 {"ili331",4},
00480 {"ili362",3},
00481 {"ili381",3},
00482 {"iln230",3},
00483 {"ici313",2},
00484 {"ici315",2},
00485 {"ici332",3},
00486 {"ici344",4},
00487 {"icn336",3},
00488 {"iwi365",3},
00489 {"ici314",2},
00490 {"ici367",2},
00491 {0,0}
00492 };
00493
00495 const char* prereqs12[] = {
00496 "dew101","dew100",
00497 "fis110","fis100",
00498 "fis110","mat121",
00499 "mat112","mat111",
00500 "mat122","mat111",
00501 "mat122","mat121",
00502 "dewxx0","dew101",
00503 "fis120","fis110",
00504 "fis120","mat122",
00505 "hcw311","hcw310",
00506 "ili142","iwi131",
00507 "mat113","mat112",
00508 "mat113","mat122",
00509 "mat123","mat112",
00510 "mat123","mat122",
00511 "fis130","fis110",
00512 "fis130","mat122",
00513 "ili134","iwi131",
00514 "ili151","mat112",
00515 "mat124","mat113",
00516 "mat124","mat123",
00517 "fis140","fis120",
00518 "fis140","fis130",
00519 "ile260","fis120",
00520 "ile260","mat124",
00521 "ili231","iwi131",
00522 "ili252","iwi131",
00523 "ili273","ili260",
00524 "mat210","mat113",
00525 "mat260","iwi131",
00526 "mat260","mat113",
00527 "mat260","mat123",
00528 "ili221","ili134",
00529 "ili221","ili231",
00530 "ili221","mat260",
00531 "ili274","ili273",
00532 "ili281","mat260",
00533 "mat270","iwi131",
00534 "mat270","mat113",
00535 "mat270","mat123",
00536 "ili238","ili134",
00537 "ili242","ili142",
00538 "ili275","ili274",
00539 "ili355","ili221",
00540 "hrw110","hrw150",
00541 "ici393","mat210",
00542 "ici393","mat260",
00543 "ili237","ili231",
00544 "ili237","ili252",
00545 "ili334","ili238",
00546 "ili363","ili273",
00547 "hrw100","hrw110",
00548 "ici382","ili334",
00549 "ili331","ili238",
00550 "ili331","ili274",
00551 "ili362","ili363",
00552 "ili381","ili281",
00553 "ili381","mat210",
00554 "iln230","iwn170",
00555 "ici313","ili331",
00556 "ici332","ici393",
00557 "ici332","ili331",
00558 "ici344","ili243",
00559 "icn336","ici393",
00560 "ici314","ici313",
00561 0,0
00562 };
00563
00565 const Curriculum curriculum[]=
00566 { { 8, 10, 24, 2, 10,
00567 courses8, prereqs8
00568 },
00569 { 10, 10, 24, 2, 10,
00570 courses10, prereqs10
00571 },
00572 { 12, 10, 24, 2, 10,
00573 courses12, prereqs12
00574 }
00575 };
00576
00578 const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
00579
00581 }
00582
00583
00584