this repo has no description
dekker.one
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
50/// A course \relates BACP
51class Course {
52public:
53 const char* name; ///< Course name
54 int credit; ///< Course credit
55};
56
57/// A curriculum \relates BACP
58class Curriculum {
59public:
60 /// Number of periods
61 int p;
62 /// Minimum academic load
63 int a;
64 /// Maximum academic load
65 int b;
66 /// Minimum amount of courses
67 int c;
68 /// Maximum amount of courses
69 int d;
70
71 /// Courses
72 const Course *courses;
73 /// Prerequisites
74 const char **prereqs;
75};
76
77namespace {
78
79 extern const Curriculum curriculum[];
80 extern const unsigned int n_examples;
81
82}
83
84/**
85 * \brief %Example: The balanced academic curriculum problem
86 *
87 * This is problem 030 from http://www.csplib.org/.
88 *
89 * A custom value selection from "A CP Approach to the Balanced
90 * Academic Curriculum Problem", J.N. Monette, P. Schaus, S. Zampelli,
91 * Y. Deville, and P. Dupont is available.
92 *
93 * \ingroup Example
94 *
95 */
96class BACP : public IntMinimizeScript {
97protected:
98 /// The curriculum to be scheduled
99 const Curriculum curr;
100
101 /// Academic load for each period
102 IntVarArray l;
103 /// Maximum academic load
104 IntVar u;
105 /// Number of courses assigned to a period
106 IntVarArray q;
107
108 /// Period to which a course is assigned
109 IntVarArray x;
110public:
111 /// Branching variants
112 enum {
113 BRANCHING_NAIVE, ///< Simple fail-first branching
114 BRANCHING_LOAD, ///< Place based on minimum-load
115 BRANCHING_LOAD_REV, ///< Place based on maximum-load
116 };
117
118 /// Actual model
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;
171 case BRANCHING_LOAD_REV:
172 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load_rev));
173 break;
174 }
175 }
176 /// Value selection function for load branching
177 static int load(const Space& home, IntVar x, int) {
178 const BACP& b = static_cast<const BACP&>(home);
179 IntVarValues values(x);
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 /// Value selection function for reverse load branching
193 static int load_rev(const Space& home, IntVar x, int) {
194 const BACP& b = static_cast<const BACP&>(home);
195 IntVarValues values(x);
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 /// Constructor for copying \a bacp
209 BACP(BACP& bacp) : IntMinimizeScript(bacp),
210 curr(bacp.curr) {
211 l.update(*this, bacp.l);
212 u.update(*this, bacp.u);
213 x.update(*this, bacp.x);
214 }
215 /// Copy during cloning
216 virtual Space*
217 copy(void) {
218 return new BACP(*this);
219 }
220 /// Return solution cost
221 virtual IntVar cost(void) const {
222 return u;
223 }
224 /// Print solution
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
245/** \brief Main-function
246 * \relates BACP
247 */
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 {
269 /** \name Parameters for balanced academic curriculum
270 * \relates BACP
271 * @{
272 */
273
274 /// Courses for first example
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
289 /// Prerequisites for first example
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
333 /// Courses for second example
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
380 /// Prerequisites for second example
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
419 /// Courses for third example
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
490 /// Prerequisites for third example
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
560 /// The example specifications
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
573 /// The number of examples
574 const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
575
576 //@}
577}
578
579// STATISTICS: example-any
580