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-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00015 * $Revision: 11473 $ 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