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) : curr(curriculum[opt.size()]) {
00124 std::map<std::string, int> courseMap;
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
00151 linear(*this, t, xij, IRT_EQ, l[j]);
00152
00153 linear(*this, xij, IRT_EQ, q[j]);
00154 }
00155
00156
00157 for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
00158 rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
00159
00160
00161 max(*this, l, u);
00162
00163
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
00583