Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
48 using namespace Gecode;
49 
51 class Course {
52 public:
53  const char* name;
54  int credit;
55 };
56 
58 class Curriculum {
59 public:
61  int p;
63  int a;
65  int b;
67  int c;
69  int d;
70 
72  const Course *courses;
74  const char **prereqs;
75 };
76 
77 namespace {
78 
79  extern const Curriculum curriculum[];
80  extern const unsigned int n_examples;
81 
82 }
83 
96 class BACP : public IntMinimizeScript {
97 protected:
100 
107 
110 public:
112  enum {
116  };
117 
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  }
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  }
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  }
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 
248 int
249 main(int argc, char* argv[]) {
250  SizeOptions opt("BACP");
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 
268 namespace {
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 
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
Definition: aliases.hpp:143
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::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
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
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
virtual Space * copy(void)
Copy during cloning.
Definition: bacp.cpp:217
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
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
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
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:461
void branching(int v)
Set default branching value.
Definition: options.hpp:225
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:283
Options for scripts with additional size parameter
Definition: driver.hh:675
Computation spaces.
Definition: core.hpp:1742
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, FloatVal n)
Propagates .
Definition: rel.cpp:43
@ IRT_EQ
Equality ( )
Definition: int.hh:926
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition: val.hpp:95
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:206
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const int min
Smallest allowed integer value.
Definition: int.hh:118
const int max
Largest allowed integer value.
Definition: int.hh:116
unsigned int size(I &i)
Size of all ranges of range iterator i.
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