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