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 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;
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
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
00162 max(*this, l, u);
00163
00164
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
00597