Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.9.4
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
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 }
264 IntMinimizeScript::run<BACP,BAB,SizeOptions>(opt);
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
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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
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
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
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
@ 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
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 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
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition: branch.cpp:120
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
unsigned int size(I &i)
Size of all ranges of range iterator i.
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
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition: var.hpp:206
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int v[7]
Definition: distinct.cpp:259
Options opt
The options.
Definition: test.cpp:97