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 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 #include <map>
00043 #include <string>
00044 #include <list>
00045 #include <vector>
00046
00047 using namespace Gecode;
00048
00050 class Course {
00051 public:
00052 const char* name;
00053 int credit;
00054 };
00055
00057 class Curriculum {
00058 public:
00060 int p;
00062 int a;
00064 int b;
00066 int c;
00068 int d;
00069
00071 const Course *courses;
00073 const char **prereqs;
00074 };
00075
00076 namespace {
00077
00078 extern const Curriculum curriculum[];
00079 extern const unsigned int n_examples;
00080
00081 }
00082
00091 class BACP : public MinimizeScript {
00092 protected:
00094 const Curriculum curr;
00095
00097 IntVarArray l;
00099 IntVar u;
00101 IntVarArray q;
00102
00104 IntVarArray x;
00105 public:
00107 BACP(const SizeOptions& opt) : curr(curriculum[opt.size()]) {
00108 int p = curr.p;
00109 int a = curr.a;
00110 int b = curr.b;
00111 int c = curr.c;
00112 int d = curr.d;
00113
00114 std::map<std::string, int> courseMap;
00115 int maxCredit = 0;
00116 int numberOfCourses = 0;
00117 for (const Course* c=curr.courses; c->name != 0; c++) {
00118 courseMap[c->name] = numberOfCourses++;
00119 maxCredit += c->credit;
00120 }
00121
00122 l = IntVarArray(*this, p, a, b);
00123 u = IntVar(*this, 0, maxCredit);
00124 q = IntVarArray(*this, p, c, d);
00125 x = IntVarArray(*this, numberOfCourses, 0, p-1);
00126
00127 for (int j=0; j<p; j++) {
00128 BoolVarArray xij(*this, numberOfCourses, 0, 1);
00129 IntArgs t(numberOfCourses);
00130 for (int i=0; i<numberOfCourses; i++) {
00131 post(*this, tt(eqv(~(x[i]==j), xij[i])));
00132 t[i] = curr.courses[i].credit;
00133 }
00134
00135 linear(*this, t, xij, IRT_EQ, l[j]);
00136
00137 linear(*this, xij, IRT_EQ, q[j]);
00138 }
00139
00140
00141 for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2) {
00142 post(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
00143 }
00144
00145
00146 max(*this, l, u);
00147
00148
00149 linear(*this, l, IRT_EQ, maxCredit);
00150 linear(*this, q, IRT_EQ, numberOfCourses);
00151
00152 branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00153 }
00154
00156 BACP(bool share, BACP& bacp) : MinimizeScript(share,bacp),
00157 curr(bacp.curr) {
00158 u.update(*this, share, bacp.u);
00159 x.update(*this, share, bacp.x);
00160 }
00162 virtual Space*
00163 copy(bool share) {
00164 return new BACP(share,*this);
00165 }
00167 virtual IntVar cost(void) const {
00168 return u;
00169 }
00171 virtual void
00172 print(std::ostream& os) const {
00173 std::vector<std::list<int> > period(curr.p);
00174 for (int i=x.size(); i--;)
00175 period[x[i].val()].push_back(i);
00176
00177 os << "Solution with load " << u.val() << ":" << std::endl;
00178 for (int i=0; i<curr.p; i++) {
00179 os << "\tPeriod "<<i+1<<": ";
00180 for (std::list<int>::iterator v=period[i].begin();
00181 v != period[i].end(); ++v) {
00182 os << curr.courses[*v].name << " ";
00183 }
00184 os << std::endl;
00185 }
00186 os << std::endl;
00187 }
00188 };
00189
00193 int
00194 main(int argc, char* argv[]) {
00195 SizeOptions opt("BACP");
00196 opt.size(2);
00197 opt.solutions(0);
00198 opt.iterations(20);
00199 opt.parse(argc,argv);
00200 if (opt.size() >= n_examples) {
00201 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00202 << std::endl;
00203 return 1;
00204 }
00205 MinimizeScript::run<BACP,BAB,SizeOptions>(opt);
00206 return 0;
00207 }
00208
00209 namespace {
00215
00216 const Course courses8[] =
00217 {
00218 {"dew100", 1},
00219 {"fis100", 3},
00220 {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
00221 {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
00222 {"iei134", 3},{"iei141", 3},{"mat194", 4},
00223 {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
00224 {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
00225 {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
00226 {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
00227 {0,0}
00228 };
00229
00231 const char* prereqs8[] =
00232 {
00233 "dew101","dew100",
00234 "fis101","fis100",
00235 "fis101","mat192",
00236 "mat191","mat190",
00237 "mat193","mat190",
00238 "mat193","mat192",
00239 "fis102","fis101",
00240 "fis102","mat193",
00241 "iei134","iwi131",
00242 "iei141","iwi131",
00243 "mat194","mat191 ",
00244 "mat194","mat193",
00245 "dewxx0","dew101",
00246 "hcw311","hcw310",
00247 "iei132","iei134",
00248 "iei133","iei134",
00249 "iei142","iei141",
00250 "mat195","mat194",
00251 "iei231","iei134",
00252 "iei241","iei142",
00253 "iei271","iei162",
00254 "iei281","mat195",
00255 "iei233","iei231",
00256 "iei238","iei231",
00257 "iei261","iwn261",
00258 "iei272","iei271",
00259 "iei273","iei271",
00260 "iei273","iei271",
00261 "iei161","iwn261",
00262 "iei161","iwn261",
00263 "iei232","iei273",
00264 "iei232","iei273",
00265 "iei262","iwn261",
00266 "iei274","iei273",
00267 "iei274","iei273",
00268 "iei219","iei232",
00269 "iei248","iei233",
00270 "iei248","iei233",
00271 0,0
00272 };
00273
00275 const Course courses10[] = {
00276 {"dew100",1},
00277 {"fis100",3},
00278 {"hrwxx1",2},
00279 {"iwg101",2},
00280 {"mat021",5},
00281 {"qui010",3},
00282 {"dew101",1},
00283 {"fis110",5},
00284 {"hrwxx2",2},
00285 {"iwi131",3},
00286 {"mat022",5},
00287 {"dewxx0",1},
00288 {"fis120",4},
00289 {"hcw310",1},
00290 {"hrwxx3",2},
00291 {"ili134",4},
00292 {"ili151",3},
00293 {"mat023",4},
00294 {"hcw311",1},
00295 {"ili135",4},
00296 {"ili153",3},
00297 {"ili260",3},
00298 {"iwn261",3},
00299 {"mat024",4},
00300 {"fis130",4},
00301 {"ili239",4},
00302 {"ili245",4},
00303 {"ili253",4},
00304 {"fis140",4},
00305 {"ili236",4},
00306 {"ili243",4},
00307 {"ili270",3},
00308 {"ili280",4},
00309 {"ici344",4},
00310 {"ili263",3},
00311 {"ili332",4},
00312 {"ili355",4},
00313 {"iwn170",3},
00314 {"icdxx1",3},
00315 {"ili362",3},
00316 {"iwn270",3},
00317 {"icdxx2",3},
00318 {0,0}
00319 };
00320
00322 const char* prereqs10[] = {
00323 "dew101","dew100",
00324 "fis110","fis100",
00325 "fis110","mat021",
00326 "mat022","mat021",
00327 "dewxx0","dew101",
00328 "fis120","fis110",
00329 "fis120","mat022",
00330 "ili134","iwi131",
00331 "ili151","iwi131",
00332 "mat023","mat022",
00333 "hcw311","hcw310",
00334 "ili135","ili134",
00335 "ili153","ili134",
00336 "ili153","ili151",
00337 "mat024","mat023",
00338 "fis130","fis110",
00339 "fis130","mat022",
00340 "ili239","ili135",
00341 "ili245","ili153",
00342 "ili253","ili153",
00343 "fis140","fis120",
00344 "fis140","fis130",
00345 "ili236","ili239",
00346 "ili243","ili245",
00347 "ili270","ili260",
00348 "ili270","iwn261",
00349 "ili280","mat024",
00350 "ici344","ili243",
00351 "ili263","ili260",
00352 "ili263","iwn261",
00353 "ili332","ili236",
00354 "ili355","ili153",
00355 "ili355","ili280",
00356 "ili362","ili263",
00357 0,0
00358 };
00359
00361 const Course courses12[] = {
00362 {"dew100",1},
00363 {"fis100",3},
00364 {"hcw310",1},
00365 {"iwg101",2},
00366 {"mat111",4},
00367 {"mat121",4},
00368 {"dew101",1},
00369 {"fis110",5},
00370 {"iwi131",3},
00371 {"mat112",4},
00372 {"mat122",4},
00373 {"dewxx0",1},
00374 {"fis120",4},
00375 {"hcw311",1},
00376 {"hxwxx1",1},
00377 {"ili142",4},
00378 {"mat113",4},
00379 {"mat123",4},
00380 {"fis130",4},
00381 {"ili134",4},
00382 {"ili151",3},
00383 {"iwm185",3},
00384 {"mat124",4},
00385 {"fis140",4},
00386 {"hxwxx2",1},
00387 {"ile260",3},
00388 {"ili260",3},
00389 {"iwn170",3},
00390 {"qui104",3},
00391 {"ili231",3},
00392 {"ili243",4},
00393 {"ili252",4},
00394 {"ili273",3},
00395 {"mat210",4},
00396 {"mat260",4},
00397 {"ild208",3},
00398 {"ili221",4},
00399 {"ili274",3},
00400 {"ili281",3},
00401 {"iwn270",3},
00402 {"mat270",4},
00403 {"hrw150",2},
00404 {"ili238",4},
00405 {"ili242",3},
00406 {"ili275",3},
00407 {"ili355",4},
00408 {"hrw110",2},
00409 {"ici393",4},
00410 {"ili237",4},
00411 {"ili334",4},
00412 {"ili363",3},
00413 {"iwn261",3},
00414 {"hrw100",2},
00415 {"ici382",4},
00416 {"ili331",4},
00417 {"ili362",3},
00418 {"ili381",3},
00419 {"iln230",3},
00420 {"ici313",2},
00421 {"ici315",2},
00422 {"ici332",3},
00423 {"ici344",4},
00424 {"icn336",3},
00425 {"iwi365",3},
00426 {"ici314",2},
00427 {"ici367",2},
00428 {0,0}
00429 };
00430
00432 const char* prereqs12[] = {
00433 "dew101","dew100",
00434 "fis110","fis100",
00435 "fis110","mat121",
00436 "mat112","mat111",
00437 "mat122","mat111",
00438 "mat122","mat121",
00439 "dewxx0","dew101",
00440 "fis120","fis110",
00441 "fis120","mat122",
00442 "hcw311","hcw310",
00443 "ili142","iwi131",
00444 "mat113","mat112",
00445 "mat113","mat122",
00446 "mat123","mat112",
00447 "mat123","mat122",
00448 "fis130","fis110",
00449 "fis130","mat122",
00450 "ili134","iwi131",
00451 "ili151","mat112",
00452 "mat124","mat113",
00453 "mat124","mat123",
00454 "fis140","fis120",
00455 "fis140","fis130",
00456 "ile260","fis120",
00457 "ile260","mat124",
00458 "ili231","iwi131",
00459 "ili252","iwi131",
00460 "ili273","ili260",
00461 "mat210","mat113",
00462 "mat260","iwi131",
00463 "mat260","mat113",
00464 "mat260","mat123",
00465 "ili221","ili134",
00466 "ili221","ili231",
00467 "ili221","mat260",
00468 "ili274","ili273",
00469 "ili281","mat260",
00470 "mat270","iwi131",
00471 "mat270","mat113",
00472 "mat270","mat123",
00473 "ili238","ili134",
00474 "ili242","ili142",
00475 "ili275","ili274",
00476 "ili355","ili221",
00477 "hrw110","hrw150",
00478 "ici393","mat210",
00479 "ici393","mat260",
00480 "ili237","ili231",
00481 "ili237","ili252",
00482 "ili334","ili238",
00483 "ili363","ili273",
00484 "hrw100","hrw110",
00485 "ici382","ili334",
00486 "ili331","ili238",
00487 "ili331","ili274",
00488 "ili362","ili363",
00489 "ili381","ili281",
00490 "ili381","mat210",
00491 "iln230","iwn170",
00492 "ici313","ili331",
00493 "ici332","ici393",
00494 "ici332","ili331",
00495 "ici344","ili243",
00496 "icn336","ici393",
00497 "ici314","ici313",
00498 0,0
00499 };
00500
00502 const Curriculum curriculum[]=
00503 { { 8, 10, 24, 2, 10,
00504 courses8, prereqs8
00505 },
00506 { 10, 10, 24, 2, 10,
00507 courses10, prereqs10
00508 },
00509 { 12, 10, 24, 2, 10,
00510 courses12, prereqs12
00511 }
00512 };
00513
00515 const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
00516
00518 }
00519
00520
00521