Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
bacp.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Contributing authors:
7 * Mikael Lagerkvist <lagerkvist@gecode.org>
8 *
9 * Copyright:
10 * Guido Tack, 2006
11 * Mikael Lagerkvist, 2010
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40#include <gecode/minimodel.hh>
41#include <gecode/int/branch.hh>
42
43#include <map>
44#include <string>
45#include <list>
46#include <vector>
47
48using namespace Gecode;
49
51class Course {
52public:
53 const char* name;
54 int credit;
55};
56
59public:
61 int p;
63 int a;
65 int b;
67 int c;
69 int d;
70
74 const char **prereqs;
75};
76
77namespace {
78
79 extern const Curriculum curriculum[];
80 extern const unsigned int n_examples;
81
82}
83
96class BACP : public IntMinimizeScript {
97protected:
100
107
110public:
112 enum {
116 };
117
119 BACP(const SizeOptions& opt)
120 : IntMinimizeScript(opt), curr(curriculum[opt.size()]) {
121 std::map<std::string, int> courseMap; // Map names to course numbers
122 int maxCredit = 0;
123 int numberOfCourses = 0;
124 for (const Course* co=curr.courses; co->name != 0; co++) {
125 courseMap[co->name] = numberOfCourses++;
126 maxCredit += co->credit;
127 }
128
129 int p = curr.p;
130 int a = curr.a;
131 int b = curr.b;
132 int c = curr.c;
133 int d = curr.d;
134
135 l = IntVarArray(*this, p, a, b);
136 u = IntVar(*this, 0, maxCredit);
137 q = IntVarArray(*this, p, c, d);
138 x = IntVarArray(*this, numberOfCourses, 0, p-1);
139
140 for (int j=0; j<p; j++) {
141 BoolVarArgs xij(*this, numberOfCourses, 0, 1);
142 IntArgs t(numberOfCourses);
143 for (int i=0; i<numberOfCourses; i++) {
144 rel(*this, (x[i]==j) == xij[i]);
145 t[i] = curr.courses[i].credit;
146 }
147 // sum over all t*(xi==j) is load of period i
148 linear(*this, t, xij, IRT_EQ, l[j]);
149 // sum over all (xi==j) is number of courses in period i
150 linear(*this, xij, IRT_EQ, q[j]);
151 }
152
153 // Precedence
154 for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
155 rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
156
157 // Optimization criterion: minimize u
158 max(*this, l, u);
159
160 // Redundant constraints
161 linear(*this, l, IRT_EQ, maxCredit);
162 linear(*this, q, IRT_EQ, numberOfCourses);
163
164 switch (opt.branching()) {
165 case BRANCHING_NAIVE:
166 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
167 break;
168 case BRANCHING_LOAD:
169 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load));
170 break;
173 break;
174 }
175 }
176
177 static int load(const Space& home, IntVar x, int) {
178 const BACP& b = static_cast<const BACP&>(home);
180 int val = -1;
181 int best = Int::Limits::max+1;
182 while (values()) {
183 if (b.l[values.val()].min() < best) {
184 val = values.val();
185 best = b.l[val].min();
186 }
187 ++values;
188 }
189 assert(val != -1);
190 return val;
191 }
192
193 static int load_rev(const Space& home, IntVar x, int) {
194 const BACP& b = static_cast<const BACP&>(home);
196 int val = -1;
197 int best = Int::Limits::min-1;
198 while (values()) {
199 if (b.l[values.val()].min() > best) {
200 val = values.val();
201 best = b.l[val].min();
202 }
203 ++values;
204 }
205 assert(val != -1);
206 return val;
207 }
208
210 curr(bacp.curr) {
211 l.update(*this, bacp.l);
212 u.update(*this, bacp.u);
213 x.update(*this, bacp.x);
214 }
215
216 virtual Space*
217 copy(void) {
218 return new BACP(*this);
219 }
220
221 virtual IntVar cost(void) const {
222 return u;
223 }
224
225 virtual void
226 print(std::ostream& os) const {
227 std::vector<std::list<int> > period(curr.p);
228 for (int i=x.size(); i--;)
229 period[x[i].val()].push_back(i);
230
231 os << "Solution with load " << u.val() << ":" << std::endl;
232 for (int i=0; i<curr.p; i++) {
233 os << "\tPeriod "<<i+1<<": ";
234 for (std::list<int>::iterator v=period[i].begin();
235 v != period[i].end(); ++v) {
236 os << curr.courses[*v].name << " ";
237 }
238 os << std::endl;
239 }
240 os << std::endl;
241 }
242
243};
244
248int
249main(int argc, char* argv[]) {
250 SizeOptions opt("BACP");
251 opt.branching(BACP::BRANCHING_NAIVE);
252 opt.branching(BACP::BRANCHING_NAIVE,"naive");
253 opt.branching(BACP::BRANCHING_LOAD,"load");
254 opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
255 opt.size(2);
256 opt.solutions(0);
257 opt.iterations(20);
258 opt.parse(argc,argv);
259 if (opt.size() >= n_examples) {
260 std::cerr << "Error: size must be between 0 and " << n_examples - 1
261 << std::endl;
262 return 1;
263 }
265 return 0;
266}
267
268namespace {
273
275 const Course courses8[] =
276 {
277 {"dew100", 1},
278 {"fis100", 3},
279 {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
280 {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
281 {"iei134", 3},{"iei141", 3},{"mat194", 4},
282 {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
283 {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
284 {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
285 {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
286 {0,0}
287 };
288
290 const char* prereqs8[] =
291 {
292 "dew101","dew100",
293 "fis101","fis100",
294 "fis101","mat192",
295 "mat191","mat190",
296 "mat193","mat190",
297 "mat193","mat192",
298 "fis102","fis101",
299 "fis102","mat193",
300 "iei134","iwi131",
301 "iei141","iwi131",
302 "mat194","mat191 ",
303 "mat194","mat193",
304 "dewxx0","dew101",
305 "hcw311","hcw310",
306 "iei132","iei134",
307 "iei133","iei134",
308 "iei142","iei141",
309 "mat195","mat194",
310 "iei231","iei134",
311 "iei241","iei142",
312 "iei271","iei162",
313 "iei281","mat195",
314 "iei233","iei231",
315 "iei238","iei231",
316 "iei261","iwn261",
317 "iei272","iei271",
318 "iei273","iei271",
319 "iei273","iei271",
320 "iei161","iwn261",
321 "iei161","iwn261",
322 "iei232","iei273",
323 "iei232","iei273",
324 "iei262","iwn261",
325 "iei274","iei273",
326 "iei274","iei273",
327 "iei219","iei232",
328 "iei248","iei233",
329 "iei248","iei233",
330 0,0
331 };
332
334 const Course courses10[] = {
335 {"dew100",1},
336 {"fis100",3},
337 {"hrwxx1",2},
338 {"iwg101",2},
339 {"mat021",5},
340 {"qui010",3},
341 {"dew101",1},
342 {"fis110",5},
343 {"hrwxx2",2},
344 {"iwi131",3},
345 {"mat022",5},
346 {"dewxx0",1},
347 {"fis120",4},
348 {"hcw310",1},
349 {"hrwxx3",2},
350 {"ili134",4},
351 {"ili151",3},
352 {"mat023",4},
353 {"hcw311",1},
354 {"ili135",4},
355 {"ili153",3},
356 {"ili260",3},
357 {"iwn261",3},
358 {"mat024",4},
359 {"fis130",4},
360 {"ili239",4},
361 {"ili245",4},
362 {"ili253",4},
363 {"fis140",4},
364 {"ili236",4},
365 {"ili243",4},
366 {"ili270",3},
367 {"ili280",4},
368 {"ici344",4},
369 {"ili263",3},
370 {"ili332",4},
371 {"ili355",4},
372 {"iwn170",3},
373 {"icdxx1",3},
374 {"ili362",3},
375 {"iwn270",3},
376 {"icdxx2",3},
377 {0,0}
378 };
379
381 const char* prereqs10[] = {
382 "dew101","dew100",
383 "fis110","fis100",
384 "fis110","mat021",
385 "mat022","mat021",
386 "dewxx0","dew101",
387 "fis120","fis110",
388 "fis120","mat022",
389 "ili134","iwi131",
390 "ili151","iwi131",
391 "mat023","mat022",
392 "hcw311","hcw310",
393 "ili135","ili134",
394 "ili153","ili134",
395 "ili153","ili151",
396 "mat024","mat023",
397 "fis130","fis110",
398 "fis130","mat022",
399 "ili239","ili135",
400 "ili245","ili153",
401 "ili253","ili153",
402 "fis140","fis120",
403 "fis140","fis130",
404 "ili236","ili239",
405 "ili243","ili245",
406 "ili270","ili260",
407 "ili270","iwn261",
408 "ili280","mat024",
409 "ici344","ili243",
410 "ili263","ili260",
411 "ili263","iwn261",
412 "ili332","ili236",
413 "ili355","ili153",
414 "ili355","ili280",
415 "ili362","ili263",
416 0,0
417 };
418
420 const Course courses12[] = {
421 {"dew100",1},
422 {"fis100",3},
423 {"hcw310",1},
424 {"iwg101",2},
425 {"mat111",4},
426 {"mat121",4},
427 {"dew101",1},
428 {"fis110",5},
429 {"iwi131",3},
430 {"mat112",4},
431 {"mat122",4},
432 {"dewxx0",1},
433 {"fis120",4},
434 {"hcw311",1},
435 {"hxwxx1",1},
436 {"ili142",4},
437 {"mat113",4},
438 {"mat123",4},
439 {"fis130",4},
440 {"ili134",4},
441 {"ili151",3},
442 {"iwm185",3},
443 {"mat124",4},
444 {"fis140",4},
445 {"hxwxx2",1},
446 {"ile260",3},
447 {"ili260",3},
448 {"iwn170",3},
449 {"qui104",3},
450 {"ili231",3},
451 {"ili243",4},
452 {"ili252",4},
453 {"ili273",3},
454 {"mat210",4},
455 {"mat260",4},
456 {"ild208",3},
457 {"ili221",4},
458 {"ili274",3},
459 {"ili281",3},
460 {"iwn270",3},
461 {"mat270",4},
462 {"hrw150",2},
463 {"ili238",4},
464 {"ili242",3},
465 {"ili275",3},
466 {"ili355",4},
467 {"hrw110",2},
468 {"ici393",4},
469 {"ili237",4},
470 {"ili334",4},
471 {"ili363",3},
472 {"iwn261",3},
473 {"hrw100",2},
474 {"ici382",4},
475 {"ili331",4},
476 {"ili362",3},
477 {"ili381",3},
478 {"iln230",3},
479 {"ici313",2},
480 {"ici315",2},
481 {"ici332",3},
482 {"ici344",4},
483 {"icn336",3},
484 {"iwi365",3},
485 {"ici314",2},
486 {"ici367",2},
487 {0,0}
488 };
489
491 const char* prereqs12[] = {
492 "dew101","dew100",
493 "fis110","fis100",
494 "fis110","mat121",
495 "mat112","mat111",
496 "mat122","mat111",
497 "mat122","mat121",
498 "dewxx0","dew101",
499 "fis120","fis110",
500 "fis120","mat122",
501 "hcw311","hcw310",
502 "ili142","iwi131",
503 "mat113","mat112",
504 "mat113","mat122",
505 "mat123","mat112",
506 "mat123","mat122",
507 "fis130","fis110",
508 "fis130","mat122",
509 "ili134","iwi131",
510 "ili151","mat112",
511 "mat124","mat113",
512 "mat124","mat123",
513 "fis140","fis120",
514 "fis140","fis130",
515 "ile260","fis120",
516 "ile260","mat124",
517 "ili231","iwi131",
518 "ili252","iwi131",
519 "ili273","ili260",
520 "mat210","mat113",
521 "mat260","iwi131",
522 "mat260","mat113",
523 "mat260","mat123",
524 "ili221","ili134",
525 "ili221","ili231",
526 "ili221","mat260",
527 "ili274","ili273",
528 "ili281","mat260",
529 "mat270","iwi131",
530 "mat270","mat113",
531 "mat270","mat123",
532 "ili238","ili134",
533 "ili242","ili142",
534 "ili275","ili274",
535 "ili355","ili221",
536 "hrw110","hrw150",
537 "ici393","mat210",
538 "ici393","mat260",
539 "ili237","ili231",
540 "ili237","ili252",
541 "ili334","ili238",
542 "ili363","ili273",
543 "hrw100","hrw110",
544 "ici382","ili334",
545 "ili331","ili238",
546 "ili331","ili274",
547 "ili362","ili363",
548 "ili381","ili281",
549 "ili381","mat210",
550 "iln230","iwn170",
551 "ici313","ili331",
552 "ici332","ici393",
553 "ici332","ili331",
554 "ici344","ili243",
555 "icn336","ici393",
556 "ici314","ici313",
557 0,0
558 };
559
562 { { 8, 10, 24, 2, 10,
564 },
565 { 10, 10, 24, 2, 10,
567 },
568 { 12, 10, 24, 2, 10,
570 }
571 };
572
574 const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
575
577}
578
579// STATISTICS: example-any
580
int main(int argc, char *argv[])
Main-function.
Definition bacp.cpp:249
const Curriculum curriculum[]
The example specifications.
Definition bacp.cpp:561
const char * prereqs10[]
Prerequisites for second example.
Definition bacp.cpp:381
const Course courses10[]
Courses for second example.
Definition bacp.cpp:334
const unsigned int n_examples
The number of examples.
Definition bacp.cpp:574
const Course courses8[]
Courses for first example.
Definition bacp.cpp:275
virtual void print(std::ostream &os) const
Print solution.
Definition bacp.cpp:226
const Curriculum curr
The curriculum to be scheduled.
Definition bacp.cpp:99
const char * prereqs12[]
Prerequisites for third example.
Definition bacp.cpp:491
static int load(const Space &home, IntVar x, int)
Value selection function for load branching.
Definition bacp.cpp:177
IntVarArray l
Academic load for each period.
Definition bacp.cpp:102
virtual Space * copy(void)
Copy during cloning.
Definition bacp.cpp:217
IntVar u
Maximum academic load.
Definition bacp.cpp:104
@ BRANCHING_NAIVE
Simple fail-first branching.
Definition bacp.cpp:113
@ BRANCHING_LOAD
Place based on minimum-load.
Definition bacp.cpp:114
@ BRANCHING_LOAD_REV
Place based on maximum-load.
Definition bacp.cpp:115
static int load_rev(const Space &home, IntVar x, int)
Value selection function for reverse load branching.
Definition bacp.cpp:193
IntVarArray x
Period to which a course is assigned.
Definition bacp.cpp:109
BACP(const SizeOptions &opt)
Actual model.
Definition bacp.cpp:119
const Course courses12[]
Courses for third example.
Definition bacp.cpp:420
IntVarArray q
Number of courses assigned to a period.
Definition bacp.cpp:106
BACP(BACP &bacp)
Constructor for copying bacp.
Definition bacp.cpp:209
const char * prereqs8[]
Prerequisites for first example.
Definition bacp.cpp:290
virtual IntVar cost(void) const
Return solution cost.
Definition bacp.cpp:221
A course.
Definition bacp.cpp:51
const char * name
Course name.
Definition bacp.cpp:53
int credit
Course credit.
Definition bacp.cpp:54
A curriculum.
Definition bacp.cpp:58
int p
Number of periods.
Definition bacp.cpp:61
const Course * courses
Courses.
Definition bacp.cpp:72
int c
Minimum amount of courses.
Definition bacp.cpp:67
int d
Maximum amount of courses.
Definition bacp.cpp:69
int a
Minimum academic load.
Definition bacp.cpp:63
const char ** prereqs
Prerequisites.
Definition bacp.cpp:74
int b
Maximum academic load.
Definition bacp.cpp:65
Passing Boolean variables.
Definition int.hh:721
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Passing integer arguments.
Definition int.hh:634
Integer variable array.
Definition int.hh:772
Value iterator for integer variables.
Definition int.hh:493
Integer variables.
Definition int.hh:371
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:808
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:941
const int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode toplevel namespace
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c=nullptr)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition val.hpp:95
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206