Generated on Thu Feb 21 2013 23:11:38 for Gecode by doxygen 1.8.3.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: 2011-09-19 22:02:26 +1000 (Mon, 19 Sep 2011) $ by $Author: schulte $
15  * $Revision: 12400 $
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 MinimizeScript {
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  if (opt.branching() == BRANCHING_NAIVE) {
168  branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN);
169  } else {
171  ViewArray<Int::IntView> xv(*this, IntVarArgs(x));
172  if (opt.branching() == BRANCHING_LOAD) {
175  ::post(*this,xv,varsel,valsel);
176  } else {
179  ::post(*this,xv,varsel,valsel);
180  }
181  }
182  }
183 
185  BACP(bool share, BACP& bacp) : MinimizeScript(share,bacp),
186  curr(bacp.curr) {
187  l.update(*this, share, bacp.l);
188  u.update(*this, share, bacp.u);
189  x.update(*this, share, bacp.x);
190  }
192  virtual Space*
193  copy(bool share) {
194  return new BACP(share,*this);
195  }
197  virtual IntVar cost(void) const {
198  return u;
199  }
201  virtual void
202  print(std::ostream& os) const {
203  std::vector<std::list<int> > period(curr.p);
204  for (int i=x.size(); i--;)
205  period[x[i].val()].push_back(i);
206 
207  os << "Solution with load " << u.val() << ":" << std::endl;
208  for (int i=0; i<curr.p; i++) {
209  os << "\tPeriod "<<i+1<<": ";
210  for (std::list<int>::iterator v=period[i].begin();
211  v != period[i].end(); ++v) {
212  os << curr.courses[*v].name << " ";
213  }
214  os << std::endl;
215  }
216  os << std::endl;
217  }
218 
225  template <bool minimize>
226  class ValBestLoad : public ValSelBase<Int::IntView,int> {
227  public:
229  ValBestLoad(void) {}
230 
232  ValBestLoad(Space& home, const ValBranchOptions& vbo)
233  : ValSelBase<Int::IntView,int>(home,vbo) {}
234 
236  int val(Space& home, Int::IntView x) const {
237  BACP& b = static_cast<BACP&>(home);
239  int val = -1;
240  int best = minimize ? Int::Limits::max+1 : Int::Limits::min-1;
241  while (values()) {
242  if (minimize
243  ? b.l[values.val()].min() < best
244  : b.l[values.val()].min() > best) {
245  val = values.val();
246  best = b.l[val].min();
247  }
248  ++values;
249  }
250  assert(val != -1);
251  return val;
252  }
253 
255  ModEvent tell(Space& home, unsigned int a, Int::IntView x, int n) {
256  return (a == 0) ? x.eq(home,n) : x.gr(home,n);
257  }
258  };
259 };
260 
264 int
265 main(int argc, char* argv[]) {
266  SizeOptions opt("BACP");
268  opt.branching(BACP::BRANCHING_NAIVE,"naive");
269  opt.branching(BACP::BRANCHING_LOAD,"load");
270  opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
271  opt.size(2);
272  opt.solutions(0);
273  opt.iterations(20);
274  opt.parse(argc,argv);
275  if (opt.size() >= n_examples) {
276  std::cerr << "Error: size must be between 0 and " << n_examples - 1
277  << std::endl;
278  return 1;
279  }
280  MinimizeScript::run<BACP,BAB,SizeOptions>(opt);
281  return 0;
282 }
283 
284 namespace {
290 
291  const Course courses8[] =
292  {
293  {"dew100", 1},
294  {"fis100", 3},
295  {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
296  {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
297  {"iei134", 3},{"iei141", 3},{"mat194", 4},
298  {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
299  {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
300  {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
301  {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
302  {0,0}
303  };
304 
306  const char* prereqs8[] =
307  {
308  "dew101","dew100",
309  "fis101","fis100",
310  "fis101","mat192",
311  "mat191","mat190",
312  "mat193","mat190",
313  "mat193","mat192",
314  "fis102","fis101",
315  "fis102","mat193",
316  "iei134","iwi131",
317  "iei141","iwi131",
318  "mat194","mat191 ",
319  "mat194","mat193",
320  "dewxx0","dew101",
321  "hcw311","hcw310",
322  "iei132","iei134",
323  "iei133","iei134",
324  "iei142","iei141",
325  "mat195","mat194",
326  "iei231","iei134",
327  "iei241","iei142",
328  "iei271","iei162",
329  "iei281","mat195",
330  "iei233","iei231",
331  "iei238","iei231",
332  "iei261","iwn261",
333  "iei272","iei271",
334  "iei273","iei271",
335  "iei273","iei271",
336  "iei161","iwn261",
337  "iei161","iwn261",
338  "iei232","iei273",
339  "iei232","iei273",
340  "iei262","iwn261",
341  "iei274","iei273",
342  "iei274","iei273",
343  "iei219","iei232",
344  "iei248","iei233",
345  "iei248","iei233",
346  0,0
347  };
348 
350  const Course courses10[] = {
351  {"dew100",1},
352  {"fis100",3},
353  {"hrwxx1",2},
354  {"iwg101",2},
355  {"mat021",5},
356  {"qui010",3},
357  {"dew101",1},
358  {"fis110",5},
359  {"hrwxx2",2},
360  {"iwi131",3},
361  {"mat022",5},
362  {"dewxx0",1},
363  {"fis120",4},
364  {"hcw310",1},
365  {"hrwxx3",2},
366  {"ili134",4},
367  {"ili151",3},
368  {"mat023",4},
369  {"hcw311",1},
370  {"ili135",4},
371  {"ili153",3},
372  {"ili260",3},
373  {"iwn261",3},
374  {"mat024",4},
375  {"fis130",4},
376  {"ili239",4},
377  {"ili245",4},
378  {"ili253",4},
379  {"fis140",4},
380  {"ili236",4},
381  {"ili243",4},
382  {"ili270",3},
383  {"ili280",4},
384  {"ici344",4},
385  {"ili263",3},
386  {"ili332",4},
387  {"ili355",4},
388  {"iwn170",3},
389  {"icdxx1",3},
390  {"ili362",3},
391  {"iwn270",3},
392  {"icdxx2",3},
393  {0,0}
394  };
395 
397  const char* prereqs10[] = {
398  "dew101","dew100",
399  "fis110","fis100",
400  "fis110","mat021",
401  "mat022","mat021",
402  "dewxx0","dew101",
403  "fis120","fis110",
404  "fis120","mat022",
405  "ili134","iwi131",
406  "ili151","iwi131",
407  "mat023","mat022",
408  "hcw311","hcw310",
409  "ili135","ili134",
410  "ili153","ili134",
411  "ili153","ili151",
412  "mat024","mat023",
413  "fis130","fis110",
414  "fis130","mat022",
415  "ili239","ili135",
416  "ili245","ili153",
417  "ili253","ili153",
418  "fis140","fis120",
419  "fis140","fis130",
420  "ili236","ili239",
421  "ili243","ili245",
422  "ili270","ili260",
423  "ili270","iwn261",
424  "ili280","mat024",
425  "ici344","ili243",
426  "ili263","ili260",
427  "ili263","iwn261",
428  "ili332","ili236",
429  "ili355","ili153",
430  "ili355","ili280",
431  "ili362","ili263",
432  0,0
433  };
434 
436  const Course courses12[] = {
437  {"dew100",1},
438  {"fis100",3},
439  {"hcw310",1},
440  {"iwg101",2},
441  {"mat111",4},
442  {"mat121",4},
443  {"dew101",1},
444  {"fis110",5},
445  {"iwi131",3},
446  {"mat112",4},
447  {"mat122",4},
448  {"dewxx0",1},
449  {"fis120",4},
450  {"hcw311",1},
451  {"hxwxx1",1},
452  {"ili142",4},
453  {"mat113",4},
454  {"mat123",4},
455  {"fis130",4},
456  {"ili134",4},
457  {"ili151",3},
458  {"iwm185",3},
459  {"mat124",4},
460  {"fis140",4},
461  {"hxwxx2",1},
462  {"ile260",3},
463  {"ili260",3},
464  {"iwn170",3},
465  {"qui104",3},
466  {"ili231",3},
467  {"ili243",4},
468  {"ili252",4},
469  {"ili273",3},
470  {"mat210",4},
471  {"mat260",4},
472  {"ild208",3},
473  {"ili221",4},
474  {"ili274",3},
475  {"ili281",3},
476  {"iwn270",3},
477  {"mat270",4},
478  {"hrw150",2},
479  {"ili238",4},
480  {"ili242",3},
481  {"ili275",3},
482  {"ili355",4},
483  {"hrw110",2},
484  {"ici393",4},
485  {"ili237",4},
486  {"ili334",4},
487  {"ili363",3},
488  {"iwn261",3},
489  {"hrw100",2},
490  {"ici382",4},
491  {"ili331",4},
492  {"ili362",3},
493  {"ili381",3},
494  {"iln230",3},
495  {"ici313",2},
496  {"ici315",2},
497  {"ici332",3},
498  {"ici344",4},
499  {"icn336",3},
500  {"iwi365",3},
501  {"ici314",2},
502  {"ici367",2},
503  {0,0}
504  };
505 
507  const char* prereqs12[] = {
508  "dew101","dew100",
509  "fis110","fis100",
510  "fis110","mat121",
511  "mat112","mat111",
512  "mat122","mat111",
513  "mat122","mat121",
514  "dewxx0","dew101",
515  "fis120","fis110",
516  "fis120","mat122",
517  "hcw311","hcw310",
518  "ili142","iwi131",
519  "mat113","mat112",
520  "mat113","mat122",
521  "mat123","mat112",
522  "mat123","mat122",
523  "fis130","fis110",
524  "fis130","mat122",
525  "ili134","iwi131",
526  "ili151","mat112",
527  "mat124","mat113",
528  "mat124","mat123",
529  "fis140","fis120",
530  "fis140","fis130",
531  "ile260","fis120",
532  "ile260","mat124",
533  "ili231","iwi131",
534  "ili252","iwi131",
535  "ili273","ili260",
536  "mat210","mat113",
537  "mat260","iwi131",
538  "mat260","mat113",
539  "mat260","mat123",
540  "ili221","ili134",
541  "ili221","ili231",
542  "ili221","mat260",
543  "ili274","ili273",
544  "ili281","mat260",
545  "mat270","iwi131",
546  "mat270","mat113",
547  "mat270","mat123",
548  "ili238","ili134",
549  "ili242","ili142",
550  "ili275","ili274",
551  "ili355","ili221",
552  "hrw110","hrw150",
553  "ici393","mat210",
554  "ici393","mat260",
555  "ili237","ili231",
556  "ili237","ili252",
557  "ili334","ili238",
558  "ili363","ili273",
559  "hrw100","hrw110",
560  "ici382","ili334",
561  "ili331","ili238",
562  "ili331","ili274",
563  "ili362","ili363",
564  "ili381","ili281",
565  "ili381","mat210",
566  "iln230","iwn170",
567  "ici313","ili331",
568  "ici332","ici393",
569  "ici332","ili331",
570  "ici344","ili243",
571  "icn336","ici393",
572  "ici314","ici313",
573  0,0
574  };
575 
577  const Curriculum curriculum[]=
578  { { 8, 10, 24, 2, 10,
579  courses8, prereqs8
580  },
581  { 10, 10, 24, 2, 10,
582  courses10, prereqs10
583  },
584  { 12, 10, 24, 2, 10,
585  courses12, prereqs12
586  }
587  };
588 
590  const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);
591 
593 }
594 
595 // STATISTICS: example-any
596