Generated on Sat Feb 7 2015 02:01:10 for Gecode by doxygen 1.8.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  * Last modified:
14  * $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
15  * $Revision: 13820 $
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 
123  BACP(const SizeOptions& opt) : curr(curriculum[opt.size()]) {
124  std::map<std::string, int> courseMap; // Map names to course numbers
125  int maxCredit = 0;
126  int numberOfCourses = 0;
127  for (const Course* co=curr.courses; co->name != 0; co++) {
128  courseMap[co->name] = numberOfCourses++;
129  maxCredit += co->credit;
130  }
131 
132  int p = curr.p;
133  int a = curr.a;
134  int b = curr.b;
135  int c = curr.c;
136  int d = curr.d;
137 
138  l = IntVarArray(*this, p, a, b);
139  u = IntVar(*this, 0, maxCredit);
140  q = IntVarArray(*this, p, c, d);
141  x = IntVarArray(*this, numberOfCourses, 0, p-1);
142 
143  for (int j=0; j<p; j++) {
144  BoolVarArgs xij(*this, numberOfCourses, 0, 1);
145  IntArgs t(numberOfCourses);
146  for (int i=0; i<numberOfCourses; i++) {
147  rel(*this, (x[i]==j) == xij[i]);
148  t[i] = curr.courses[i].credit;
149  }
150  // sum over all t*(xi==j) is load of period i
151  linear(*this, t, xij, IRT_EQ, l[j]);
152  // sum over all (xi==j) is number of courses in period i
153  linear(*this, xij, IRT_EQ, q[j]);
154  }
155 
156  // Precedence
157  for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
158  rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);
159 
160  // Optimization criterion: minimize u
161  max(*this, l, u);
162 
163  // Redundant constraints
164  linear(*this, l, IRT_EQ, maxCredit);
165  linear(*this, q, IRT_EQ, numberOfCourses);
166 
167  switch (opt.branching()) {
168  case BRANCHING_NAIVE:
169  branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
170  break;
171  case BRANCHING_LOAD:
172  branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load));
173  break;
174  case BRANCHING_LOAD_REV:
175  branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL(&load_rev));
176  break;
177  }
178  }
180  static int load(const Space& home, IntVar x, int) {
181  const BACP& b = static_cast<const BACP&>(home);
182  IntVarValues values(x);
183  int val = -1;
184  int best = Int::Limits::max+1;
185  while (values()) {
186  if (b.l[values.val()].min() < best) {
187  val = values.val();
188  best = b.l[val].min();
189  }
190  ++values;
191  }
192  assert(val != -1);
193  return val;
194  }
196  static int load_rev(const Space& home, IntVar x, int) {
197  const BACP& b = static_cast<const BACP&>(home);
198  IntVarValues values(x);
199  int val = -1;
200  int best = Int::Limits::min-1;
201  while (values()) {
202  if (b.l[values.val()].min() > best) {
203  val = values.val();
204  best = b.l[val].min();
205  }
206  ++values;
207  }
208  assert(val != -1);
209  return val;
210  }
212  BACP(bool share, BACP& bacp) : IntMinimizeScript(share,bacp),
213  curr(bacp.curr) {
214  l.update(*this, share, bacp.l);
215  u.update(*this, share, bacp.u);
216  x.update(*this, share, bacp.x);
217  }
219  virtual Space*
220  copy(bool share) {
221  return new BACP(share,*this);
222  }
224  virtual IntVar cost(void) const {
225  return u;
226  }
228  virtual void
229  print(std::ostream& os) const {
230  std::vector<std::list<int> > period(curr.p);
231  for (int i=x.size(); i--;)
232  period[x[i].val()].push_back(i);
233 
234  os << "Solution with load " << u.val() << ":" << std::endl;
235  for (int i=0; i<curr.p; i++) {
236  os << "\tPeriod "<<i+1<<": ";
237  for (std::list<int>::iterator v=period[i].begin();
238  v != period[i].end(); ++v) {
239  os << curr.courses[*v].name << " ";
240  }
241  os << std::endl;
242  }
243  os << std::endl;
244  }
245 
246 };
247 
251 int
252 main(int argc, char* argv[]) {
253  SizeOptions opt("BACP");
255  opt.branching(BACP::BRANCHING_NAIVE,"naive");
256  opt.branching(BACP::BRANCHING_LOAD,"load");
257  opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
258  opt.size(2);
259  opt.solutions(0);
260  opt.iterations(20);
261  opt.parse(argc,argv);
262  if (opt.size() >= n_examples) {
263  std::cerr << "Error: size must be between 0 and " << n_examples - 1
264  << std::endl;
265  return 1;
266  }
267  IntMinimizeScript::run<BACP,BAB,SizeOptions>(opt);
268  return 0;
269 }
270 
271 namespace {
277  const Course courses8[] =
279  {
280  {"dew100", 1},
281  {"fis100", 3},
282  {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
283  {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
284  {"iei134", 3},{"iei141", 3},{"mat194", 4},
285  {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
286  {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
287  {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
288  {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
289  {0,0}
290  };
291 
293  const char* prereqs8[] =
294  {
295  "dew101","dew100",
296  "fis101","fis100",
297  "fis101","mat192",
298  "mat191","mat190",
299  "mat193","mat190",
300  "mat193","mat192",
301  "fis102","fis101",
302  "fis102","mat193",
303  "iei134","iwi131",
304  "iei141","iwi131",
305  "mat194","mat191 ",
306  "mat194","mat193",
307  "dewxx0","dew101",
308  "hcw311","hcw310",
309  "iei132","iei134",
310  "iei133","iei134",
311  "iei142","iei141",
312  "mat195","mat194",
313  "iei231","iei134",
314  "iei241","iei142",
315  "iei271","iei162",
316  "iei281","mat195",
317  "iei233","iei231",
318  "iei238","iei231",
319  "iei261","iwn261",
320  "iei272","iei271",
321  "iei273","iei271",
322  "iei273","iei271",
323  "iei161","iwn261",
324  "iei161","iwn261",
325  "iei232","iei273",
326  "iei232","iei273",
327  "iei262","iwn261",
328  "iei274","iei273",
329  "iei274","iei273",
330  "iei219","iei232",
331  "iei248","iei233",
332  "iei248","iei233",
333  0,0
334  };
335 
337  const Course courses10[] = {
338  {"dew100",1},
339  {"fis100",3},
340  {"hrwxx1",2},
341  {"iwg101",2},
342  {"mat021",5},
343  {"qui010",3},
344  {"dew101",1},
345  {"fis110",5},
346  {"hrwxx2",2},
347  {"iwi131",3},
348  {"mat022",5},
349  {"dewxx0",1},
350  {"fis120",4},
351  {"hcw310",1},
352  {"hrwxx3",2},
353  {"ili134",4},
354  {"ili151",3},
355  {"mat023",4},
356  {"hcw311",1},
357  {"ili135",4},
358  {"ili153",3},
359  {"ili260",3},
360  {"iwn261",3},
361  {"mat024",4},
362  {"fis130",4},
363  {"ili239",4},
364  {"ili245",4},
365  {"ili253",4},
366  {"fis140",4},
367  {"ili236",4},
368  {"ili243",4},
369  {"ili270",3},
370  {"ili280",4},
371  {"ici344",4},
372  {"ili263",3},
373  {"ili332",4},
374  {"ili355",4},
375  {"iwn170",3},
376  {"icdxx1",3},
377  {"ili362",3},
378  {"iwn270",3},
379  {"icdxx2",3},
380  {0,0}
381  };
382 
384  const char* prereqs10[] = {
385  "dew101","dew100",
386  "fis110","fis100",
387  "fis110","mat021",
388  "mat022","mat021",
389  "dewxx0","dew101",
390  "fis120","fis110",
391  "fis120","mat022",
392  "ili134","iwi131",
393  "ili151","iwi131",
394  "mat023","mat022",
395  "hcw311","hcw310",
396  "ili135","ili134",
397  "ili153","ili134",
398  "ili153","ili151",
399  "mat024","mat023",
400  "fis130","fis110",
401  "fis130","mat022",
402  "ili239","ili135",
403  "ili245","ili153",
404  "ili253","ili153",
405  "fis140","fis120",
406  "fis140","fis130",
407  "ili236","ili239",
408  "ili243","ili245",
409  "ili270","ili260",
410  "ili270","iwn261",
411  "ili280","mat024",
412  "ici344","ili243",
413  "ili263","ili260",
414  "ili263","iwn261",
415  "ili332","ili236",
416  "ili355","ili153",
417  "ili355","ili280",
418  "ili362","ili263",
419  0,0
420  };
421 
423  const Course courses12[] = {
424  {"dew100",1},
425  {"fis100",3},
426  {"hcw310",1},
427  {"iwg101",2},
428  {"mat111",4},
429  {"mat121",4},
430  {"dew101",1},
431  {"fis110",5},
432  {"iwi131",3},
433  {"mat112",4},
434  {"mat122",4},
435  {"dewxx0",1},
436  {"fis120",4},
437  {"hcw311",1},
438  {"hxwxx1",1},
439  {"ili142",4},
440  {"mat113",4},
441  {"mat123",4},
442  {"fis130",4},
443  {"ili134",4},
444  {"ili151",3},
445  {"iwm185",3},
446  {"mat124",4},
447  {"fis140",4},
448  {"hxwxx2",1},
449  {"ile260",3},
450  {"ili260",3},
451  {"iwn170",3},
452  {"qui104",3},
453  {"ili231",3},
454  {"ili243",4},
455  {"ili252",4},
456  {"ili273",3},
457  {"mat210",4},
458  {"mat260",4},
459  {"ild208",3},
460  {"ili221",4},
461  {"ili274",3},
462  {"ili281",3},
463  {"iwn270",3},
464  {"mat270",4},
465  {"hrw150",2},
466  {"ili238",4},
467  {"ili242",3},
468  {"ili275",3},
469  {"ili355",4},
470  {"hrw110",2},
471  {"ici393",4},
472  {"ili237",4},
473  {"ili334",4},
474  {"ili363",3},
475  {"iwn261",3},
476  {"hrw100",2},
477  {"ici382",4},
478  {"ili331",4},
479  {"ili362",3},
480  {"ili381",3},
481  {"iln230",3},
482  {"ici313",2},
483  {"ici315",2},
484  {"ici332",3},
485  {"ici344",4},
486  {"icn336",3},
487  {"iwi365",3},
488  {"ici314",2},
489  {"ici367",2},
490  {0,0}
491  };
492 
494  const char* prereqs12[] = {
495  "dew101","dew100",
496  "fis110","fis100",
497  "fis110","mat121",
498  "mat112","mat111",
499  "mat122","mat111",
500  "mat122","mat121",
501  "dewxx0","dew101",
502  "fis120","fis110",
503  "fis120","mat122",
504  "hcw311","hcw310",
505  "ili142","iwi131",
506  "mat113","mat112",
507  "mat113","mat122",
508  "mat123","mat112",
509  "mat123","mat122",
510  "fis130","fis110",
511  "fis130","mat122",
512  "ili134","iwi131",
513  "ili151","mat112",
514  "mat124","mat113",
515  "mat124","mat123",
516  "fis140","fis120",
517  "fis140","fis130",
518  "ile260","fis120",
519  "ile260","mat124",
520  "ili231","iwi131",
521  "ili252","iwi131",
522  "ili273","ili260",
523  "mat210","mat113",
524  "mat260","iwi131",
525  "mat260","mat113",
526  "mat260","mat123",
527  "ili221","ili134",
528  "ili221","ili231",
529  "ili221","mat260",
530  "ili274","ili273",
531  "ili281","mat260",
532  "mat270","iwi131",
533  "mat270","mat113",
534  "mat270","mat123",
535  "ili238","ili134",
536  "ili242","ili142",
537  "ili275","ili274",
538  "ili355","ili221",
539  "hrw110","hrw150",
540  "ici393","mat210",
541  "ici393","mat260",
542  "ili237","ili231",
543  "ili237","ili252",
544  "ili334","ili238",
545  "ili363","ili273",
546  "hrw100","hrw110",
547  "ici382","ili334",
548  "ili331","ili238",
549  "ili331","ili274",
550  "ili362","ili363",
551  "ili381","ili281",
552  "ili381","mat210",
553  "iln230","iwn170",
554  "ici313","ili331",
555  "ici332","ici393",
556  "ici332","ili331",
557  "ici344","ili243",
558  "icn336","ici393",
559  "ici314","ici313",
560  0,0
561  };
562 
564  const Curriculum curriculum[]=
565  { { 8, 10, 24, 2, 10,
566  courses8, prereqs8
567  },
568  { 10, 10, 24, 2, 10,
569  courses10, prereqs10
570  },
571  { 12, 10, 24, 2, 10,
572  courses12, prereqs12
573  }
574  };
575 
577  const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
578 
580 }
581 
582 // STATISTICS: example-any
583 
Value iterator for integer variables.
Definition: int.hh:469
void size(unsigned int s)
Set default size.
Definition: options.hpp:467
Options for scripts with additional size parameter
Definition: driver.hh:567
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
A course.
Definition: bacp.cpp:55
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
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:435
int c
Minimum amount of courses.
Definition: bacp.cpp:71
IntVarArray x
Period to which a course is assigned.
Definition: bacp.cpp:113
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:622
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:385
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:229
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
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:224
int credit
Course credit.
Definition: bacp.cpp:58
BACP(bool share, BACP &bacp)
Constructor for copying bacp.
Definition: bacp.cpp:212
Simple fail-first branching.
Definition: bacp.cpp:117
static int load(const Space &home, IntVar x, int)
Value selection function for load branching.
Definition: bacp.cpp:180
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:196
const Curriculum curr
The curriculum to be scheduled.
Definition: bacp.cpp:103
void branching(int v)
Set default branching value.
Definition: options.hpp:203
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
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
Integer variables.
Definition: int.hh:350
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Place based on maximum-load.
Definition: bacp.cpp:119
int p
Number of periods.
Definition: bacp.cpp:65
int val(void) const
Return assigned value.
Definition: int.hpp:60
int main(int argc, char *argv[])
Main-function.
Definition: bacp.cpp:252
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:243
virtual Space * copy(bool share)
Copy during cloning.
Definition: bacp.cpp:220
A curriculum.
Definition: bacp.cpp:62
int val(void) const
Return current value.
Place based on minimum-load.
Definition: bacp.cpp:118
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
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
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
BACP(const SizeOptions &opt)
Actual model.
Definition: bacp.cpp:123