Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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 }
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 }
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 }
210 curr(bacp.curr) {
211 l.update(*this, bacp.l);
212 u.update(*this, bacp.u);
213 x.update(*this, bacp.x);
214 }
216 virtual Space*
217 copy(void) {
218 return new BACP(*this);
219 }
221 virtual IntVar cost(void) const {
222 return u;
223 }
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 {
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
561 const Curriculum curriculum[]=
562 { { 8, 10, 24, 2, 10,
563 courses8, prereqs8
564 },
565 { 10, 10, 24, 2, 10,
566 courses10, prereqs10
567 },
568 { 12, 10, 24, 2, 10,
569 courses12, prereqs12
570 }
571 };
572
574 const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
575
577}
578
579// STATISTICS: example-any
580
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
int p
Number of positive literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Example: The balanced academic curriculum problem
Definition bacp.cpp:96
int main(int argc, char *argv[])
Main-function.
Definition bacp.cpp:249
const Curriculum curriculum[]
The example specifications.
Definition bacp.cpp:561
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
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
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
IntVarArray q
Number of courses assigned to a period.
Definition bacp.cpp:106
BACP(BACP &bacp)
Constructor for copying bacp.
Definition bacp.cpp:209
@ 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
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:712
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
Passing integer arguments.
Definition int.hh:628
Integer variable array.
Definition int.hh:763
Value iterator for integer variables.
Definition int.hh:490
Integer variables.
Definition int.hh:371
int val(void) const
Return assigned value.
Definition int.hpp:56
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
int size(void) const
Return size of array (number of elements)
Definition array.hpp:926
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
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:926
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