Generated on Tue Oct 22 2013 00:48:58 for Gecode by doxygen 1.8.4
car-sequencing.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2009
8  *
9  * Last modified:
10  * $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13820 $
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 
42 #include <iomanip>
43 
44 using namespace Gecode;
45 
46 // Problems
47 namespace {
48  // Problem data
49  extern const int* problems[];
50  // Number of problems
51  extern const unsigned int n_problems;
52 }
53 
54 namespace {
60  class CarOptions : public SizeOptions {
61  private:
63  Driver::UnsignedIntOption _maxstall;
64 
65  public:
67  CarOptions(const char* s)
68  : SizeOptions(s),
69  _maxstall("-maxstall", "Maximum numbere of stalls", 30)
70  {
71  // Add options
72  add(_maxstall);
73  }
75  void parse(int& argc, char* argv[]) {
76  SizeOptions::parse(argc,argv);
77  }
79  int maxstall(void) const { return _maxstall.value(); }
80  };
81 
82 
100  template <class View>
101  class PushToEnd : public NaryOnePropagator<View,Int::PC_INT_BND> {
102  protected:
105  int val;
106 
108  PushToEnd(Space& home, bool share, PushToEnd& p);
110  PushToEnd(Space& home, ViewArray<View>& x0, View y0, int val0);
111  public:
113  PushToEnd(Space& home, bool share, Propagator& p,
114  ViewArray<View>& x0, View y0, int val0);
116  virtual Actor* copy(Space& home, bool share);
118  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
120  static ExecStatus post(Space& home,
121  ViewArray<View>& x0, View y0, int val0);
122  };
123 
124  template <class View>
125  inline
126  PushToEnd<View>::PushToEnd(Space& home,
127  ViewArray<View>& x0, View y0, int val0)
128  : NaryOnePropagator<View,Int::PC_INT_BND>(home,x0,y0), val(val0) {}
129 
130  template <class View>
131  ExecStatus
133  ViewArray<View>& x0, View y0, int val0) {
134  (void) new (home) PushToEnd<View>(home,x0,y0,val0);
135  return ES_OK;
136  }
137 
138  template <class View>
139  inline
140  PushToEnd<View>::PushToEnd(Space& home, bool share, PushToEnd<View>& p)
141  : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p), val(p.val) {}
142 
143  template <class View>
144  inline
145  PushToEnd<View>::PushToEnd(Space& home, bool share, Propagator& p,
146  ViewArray<View>& x0, View y0, int val0)
147  : NaryOnePropagator<View,Int::PC_INT_BND>(home,share,p,x0,y0), val(val0) {}
148 
149  template <class View>
150  Actor*
151  PushToEnd<View>::copy(Space& home, bool share) {
152  return new (home) PushToEnd<View>(home,share,*this);
153  }
154 
155  template <class View>
156  ExecStatus
157  PushToEnd<View>::propagate(Space& home, const ModEventDelta&) {
158  // Find number of required positions
159  int min = 0;
160  for (int i = x.size(); i-- && x[i].min() >= val-1; ) {
161  ++min;
162  }
163  // Find number of possible positions
164  int max = 0;
165  {
166  int i = x.size();
167  while (i--) {
168  if (x[i].max() != val) break;
169  ++max;
170  if (max >= y.max()) break;
171  }
172  // No variables later than max can have value val
173  while (i--) {
174  GECODE_ME_CHECK(x[i].le(home, val));
175  }
176  }
177 
178  // Constrain y to be in {min..max}
179  GECODE_ME_CHECK(y.gq(home, min));
180  GECODE_ME_CHECK(y.lq(home, max));
181 
182  // At least the y.min() last values have value val
183  for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
184  GECODE_ME_CHECK(x[pos].eq(home, val));
185  }
186 
187  return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
188  }
189 
192  void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
193  ViewArray<Int::IntView> vx(home, x);
194  Int::IntView vy(y);
195  GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
196  }
197 
198 }
199 
200 
212 class CarSequencing : public Script {
213 public:
215  enum {
218  };
220  enum {
223  };
224 protected:
226  const int problem;
228  const int ncars;
230  const int noptions;
232  const int nclasses;
234  const int maxstall;
236  const int stallval;
238  const int endval;
245 public:
247  CarSequencing(const CarOptions& opt)
248  : problem(opt.size()),
249  ncars(problems[problem][0]),
250  noptions(problems[problem][1]),
251  nclasses(problems[problem][2]),
252  maxstall(opt.maxstall()),
254  endval(nclasses+1),
255  nstall(*this, 0, maxstall),
256  nend(*this, 0, maxstall),
257  s(*this, ncars+maxstall, 0, nclasses+1)
258  {
259  // Read problem
260  const int* probit = problems[problem] + 3;
261 
262  // Sequence requirements for the options.
263  IntArgs max(noptions), block(noptions);
264  for (int i = 0; i < noptions; ++i ) {
265  max[i] = *probit++;
266  }
267  for (int i = 0; i < noptions; ++i ) {
268  block[i] = *probit++;
269  }
270  // Number of cars per class
271  IntArgs ncc(nclasses);
272  // What classes require an option
273  IntSetArgs classes(noptions);
274  int** cdata = new int*[noptions];
275  for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
276  int* n = new int[noptions];
277  for (int i = noptions; i--; ) n[i] = 0;
278  // Read data
279  for (int c = 0; c < nclasses; ++c) {
280  probit++;
281  ncc[c] = *probit++;
282  for (int o = 0; o < noptions; ++o) {
283  if (*probit++) {
284  cdata[o][n[o]++] = c;
285  }
286  }
287  }
288  // Transfer specification data to int-sets
289  for (int o = noptions; o--; ) {
290  classes[o] = IntSet(cdata[o], n[o]);
291  delete [] cdata[o];
292  }
293  delete [] cdata;
294  delete [] n;
295 
296  // Count the cars
297  {
298  IntSetArgs c(nclasses+2);
299  for (int i = nclasses; i--; ) {
300  c[i] = IntSet(ncc[i], ncc[i]);
301  }
302  c[stallval] = IntSet(0, maxstall);
303  c[ endval] = IntSet(0, maxstall);
304  count(*this, s, c);
305  }
306 
307  // Count number of end and stalls
308  count(*this, s, stallval, IRT_EQ, nstall);
309  count(*this, s, endval, IRT_EQ, nend);
310  rel(*this, nstall+nend == maxstall);
311 
312  // Make sure nothing is overloaded
313  IntSet one(1, 1);
314  for (int o = noptions; o--; ) {
315  // sb[i] reflects if car s[i] has option o
316  BoolVarArgs sb(s.size());
317  for (int i = s.size(); i--; ) {
318  BoolVar b(*this, 0, 1);
319  dom(*this, s[i], classes[o], b);
320  sb[i] = b;
321  }
322  sequence(*this, sb, one, block[o], 0, max[o]);
323  }
324 
325  // End-markers located at end only
326  switch (opt.propagation()) {
327  case PROP_REGULAR: {
328  IntArgs notend(nclasses), notstallend(nclasses+1);
329  for (int i = nclasses; i--; ) {
330  notend[i] = i;
331  notstallend[i] = i;
332  }
333  notstallend[nclasses] = stallval;
334  REG r = *REG(notend) + REG(notstallend) + *REG(endval);
335  extensional(*this, s, r);
336  for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
337  rel(*this, (nend > i) >> (s[pos]==endval));
338  }
339  } break;
340  case PROP_CUSTOM: {
341  pushtoend(*this, s, nend, endval);
342  } break;
343  }
344 
345 
346  // Branching
347  switch (opt.branching()) {
348  case BRANCH_INORDER:
349  branch(*this, s, INT_VAR_NONE(), INT_VAL_MIN());
350  break;
351  case BRANCH_MIDDLE: {
352  IntVarArgs m(s.size());
353  int mid = s.size() / 2;
354  int pos = 0;
355  m[pos++] = s[mid];
356  for (int i = 1; i <= m.size()/2; ++i) {
357  if (mid-i >= 0)
358  m[pos++] = s[mid-i];
359  if (mid+i < s.size())
360  m[pos++] = s[mid+i];
361  }
362  assert(pos == m.size());
363  branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
364  break;
365  }
366  }
367  }
368 
370  virtual void constrain(const Space& _best) {
371  const CarSequencing& best = static_cast<const CarSequencing&>(_best);
372  rel(*this, nstall, IRT_LE, best.nstall.val());
373  }
374 
376  virtual void
377  print(std::ostream& os) const {
378  int width = nclasses > 9 ? 2 : 1;
379  const char* space = nclasses > 9 ? " " : "";
380  os << "Stall slots=" << nstall
381  << ", End slots=" << nend << std::endl;
382  int i = 0;
383  for (; i < s.size(); ++i) {
384  if (s[i].assigned()) {
385  int v = s[i].val();
386  if (v == endval) break;
387  if (v == stallval) os << space << "_ ";
388  else os << std::setw(width) << v << " ";
389  } else {
390  os << space << "? ";
391  }
392  if ((i+1)%20 == 0) os << std::endl;
393  }
394  if (i%20)
395  os << std::endl;
396  os << std::endl;
397  }
398 
400  CarSequencing(bool share, CarSequencing& cs)
401  : Script(share,cs),
402  problem(cs.problem),
403  ncars(cs.ncars),
404  noptions(cs.noptions),
405  nclasses(cs.nclasses),
406  maxstall(cs.maxstall),
407  stallval(cs.stallval),
408  endval(cs.endval)
409  {
410  nstall.update(*this, share, cs.nstall);
411  nend.update(*this, share, cs.nend);
412  s.update(*this, share, cs.s);
413  }
415  virtual Space*
416  copy(bool share) {
417  return new CarSequencing(share,*this);
418  }
419 };
420 
424 int
425 main(int argc, char* argv[]) {
426  CarOptions opt("CarSequencing");
427  opt.solutions(0);
428  opt.size(0);
429  opt.branching(CarSequencing::BRANCH_INORDER);
430  opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
431  opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
432  opt.propagation(CarSequencing::PROP_CUSTOM);
433  opt.propagation(CarSequencing::PROP_REGULAR, "regular");
434  opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
435  opt.parse(argc,argv);
436  if (opt.size() >= n_problems) {
437  std::cerr << "Error: size must be between 0 and "
438  << n_problems-1 << std::endl;
439  return 1;
440  }
441 
442  Script::run<CarSequencing,BAB,CarOptions>(opt);
443  return 0;
444 }
445 
446 
447 namespace {
449 
451  const int p0[] = {
452  10, 5, 6,
453  1, 2, 1, 2, 1,
454  2, 3, 3, 5, 5,
455  0, 1, 1, 0, 1, 1, 0,
456  1, 1, 0, 0, 0, 1, 0,
457  2, 2, 0, 1, 0, 0, 1,
458  3, 2, 0, 1, 0, 1, 0,
459  4, 2, 1, 0, 1, 0, 0,
460  5, 2, 1, 1, 0, 0, 0
461  };
462 
463  // ---------------------------------
464  // Problem 4/72 (Regin & Puget // 1)
465  // ---------------------------------
466  const int p1[] = {
467  100, 5, 22,
468  1, 2, 1, 2, 1,
469  2, 3, 3, 5, 5,
470  0, 6, 1, 0, 0, 1, 0,
471  1, 10, 1, 1, 1, 0, 0,
472  2, 2, 1, 1, 0, 0, 1,
473  3, 2, 0, 1, 1, 0, 0,
474  4, 8, 0, 0, 0, 1, 0,
475  5, 15, 0, 1, 0, 0, 0,
476  6, 1, 0, 1, 1, 1, 0,
477  7, 5, 0, 0, 1, 1, 0,
478  8, 2, 1, 0, 1, 1, 0,
479  9, 3, 0, 0, 1, 0, 0,
480  10, 2, 1, 0, 1, 0, 0,
481  11, 1, 1, 1, 1, 0, 1,
482  12, 8, 0, 1, 0, 1, 0,
483  13, 3, 1, 0, 0, 1, 1,
484  14, 10, 1, 0, 0, 0, 0,
485  15, 4, 0, 1, 0, 0, 1,
486  16, 4, 0, 0, 0, 0, 1,
487  17, 2, 1, 0, 0, 0, 1,
488  18, 4, 1, 1, 0, 0, 0,
489  19, 6, 1, 1, 0, 1, 0,
490  20, 1, 1, 0, 1, 0, 1,
491  21, 1, 1, 1, 1, 1, 1,
492  };
493 
494  // --------------------------------
495  // Problem 6/76, (Regin & Puget // 2)
496  // --------------------------------
497  const int p2[] = {
498  100, 5, 22,
499  1, 2, 1, 2, 1,
500  2, 3, 3, 5, 5,
501  0, 13, 1, 0, 0, 0, 0,
502  1, 8, 0, 0, 0, 1, 0,
503  2, 7, 0, 1, 0, 0, 0,
504  3, 1, 1, 0, 0, 1, 0,
505  4, 12, 0, 0, 1, 0, 0,
506  5, 5, 0, 1, 0, 1, 0,
507  6, 5, 0, 0, 1, 1, 0,
508  7, 6, 0, 1, 1, 0, 0,
509  8, 3, 1, 0, 0, 0, 1,
510  9, 12, 1, 1, 0, 0, 0,
511  10, 8, 1, 1, 0, 1, 0,
512  11, 2, 1, 0, 0, 1, 1,
513  12, 2, 1, 1, 1, 0, 0,
514  13, 1, 0, 1, 0, 1, 1,
515  14, 4, 1, 0, 1, 0, 0,
516  15, 4, 0, 1, 0, 0, 1,
517  16, 1, 1, 1, 0, 1, 1,
518  17, 2, 1, 0, 1, 1, 0,
519  18, 1, 0, 0, 0, 0, 1,
520  19, 1, 1, 1, 1, 1, 0,
521  20, 1, 1, 1, 0, 0, 1,
522  21, 1, 0, 1, 1, 1, 0,
523  };
524 
525  // ---------------------------------
526  // Problem 10/93, (Regin & Puget // 3)
527  // ---------------------------------
528  const int p3[] = {
529  100, 5, 25,
530  1, 2, 1, 2, 1,
531  2, 3, 3, 5, 5,
532  0, 7, 1, 0, 0, 1, 0,
533  1, 11, 1, 1, 0, 0, 0,
534  2, 1, 0, 1, 1, 1, 1,
535  3, 3, 1, 0, 1, 0, 0,
536  4, 15, 0, 1, 0, 0, 0,
537  5, 2, 1, 0, 1, 1, 0,
538  6, 8, 0, 1, 0, 1, 0,
539  7, 5, 0, 0, 1, 0, 0,
540  8, 3, 0, 0, 0, 1, 0,
541  9, 4, 0, 1, 1, 1, 0,
542  10, 5, 1, 0, 0, 0, 0,
543  11, 2, 1, 1, 1, 0, 1,
544  12, 6, 0, 1, 1, 0, 0,
545  13, 2, 0, 0, 1, 0, 1,
546  14, 2, 0, 1, 0, 0, 1,
547  15, 4, 1, 1, 1, 1, 0,
548  16, 3, 1, 0, 0, 0, 1,
549  17, 5, 1, 1, 0, 1, 0,
550  18, 2, 1, 1, 1, 0, 0,
551  19, 4, 1, 1, 0, 0, 1,
552  20, 1, 1, 0, 0, 1, 1,
553  21, 1, 1, 1, 0, 1, 1,
554  22, 1, 0, 1, 0, 1, 1,
555  23, 1, 0, 1, 1, 0, 1,
556  24, 2, 0, 0, 0, 0, 1,
557  };
558 
559  // --------------
560  // Problem 16/81,
561  // --------------
562  const int p4[] = {
563  100, 5, 26,
564  1, 2, 1, 2, 1,
565  2, 3, 3, 5, 5,
566  0, 10, 1, 0, 0, 0, 0,
567  1, 2, 0, 0, 0, 0, 1,
568  2, 8, 0, 1, 0, 1, 0,
569  3, 8, 0, 0, 0, 1, 0,
570  4, 6, 0, 1, 1, 0, 0,
571  5, 11, 0, 1, 0, 0, 0,
572  6, 3, 0, 0, 1, 0, 0,
573  7, 2, 0, 0, 1, 1, 0,
574  8, 7, 1, 1, 0, 0, 0,
575  9, 2, 1, 0, 0, 1, 1,
576  10, 4, 1, 0, 1, 0, 0,
577  11, 7, 1, 0, 0, 1, 0,
578  12, 1, 1, 1, 1, 0, 1,
579  13, 3, 0, 1, 1, 1, 0,
580  14, 4, 0, 1, 0, 0, 1,
581  15, 5, 1, 1, 1, 0, 0,
582  16, 2, 1, 1, 0, 0, 1,
583  17, 1, 1, 0, 1, 1, 1,
584  18, 2, 1, 0, 1, 1, 0,
585  19, 3, 1, 0, 0, 0, 1,
586  20, 2, 0, 1, 1, 0, 1,
587  21, 1, 0, 1, 0, 1, 1,
588  22, 3, 1, 1, 0, 1, 0,
589  23, 1, 0, 0, 1, 1, 1,
590  24, 1, 1, 1, 1, 1, 1,
591  25, 1, 1, 1, 1, 1, 0,
592  };
593 
594  // ----------------------------------
595  // Problem 19/71, (Regin & Puget // 4)
596  // ----------------------------------
597  const int p5[] = {
598  100, 5, 23,
599  1, 2, 1, 2, 1,
600  2, 3, 3, 5, 5,
601  0, 2, 0, 0, 0, 1, 1,
602  1, 2, 0, 0, 1, 0, 1,
603  2, 5, 0, 1, 1, 1, 0,
604  3, 4, 0, 0, 0, 1, 0,
605  4, 4, 0, 1, 0, 1, 0,
606  5, 1, 1, 1, 0, 0, 1,
607  6, 3, 1, 1, 1, 0, 1,
608  7, 4, 0, 0, 1, 0, 0,
609  8, 19, 0, 1, 0, 0, 0,
610  9, 7, 1, 1, 0, 1, 0,
611  10, 10, 1, 0, 0, 0, 0,
612  11, 1, 0, 0, 1, 1, 0,
613  12, 5, 1, 1, 1, 1, 0,
614  13, 2, 1, 0, 1, 1, 0,
615  14, 6, 1, 1, 0, 0, 0,
616  15, 4, 1, 1, 1, 0, 0,
617  16, 8, 1, 0, 0, 1, 0,
618  17, 1, 1, 0, 0, 0, 1,
619  18, 4, 0, 1, 1, 0, 0,
620  19, 2, 0, 0, 0, 0, 1,
621  20, 4, 0, 1, 0, 0, 1,
622  21, 1, 1, 1, 0, 1, 1,
623  22, 1, 0, 1, 1, 0, 1,
624  };
625 
626  const int* problems[] = {
627  &p0[0],
628  &p1[0],
629  &p2[0],
630  &p3[0],
631  &p4[0],
632  &p5[0],
633  };
634 
636  const unsigned int n_problems = sizeof(problems)/sizeof(int*);
637 };
638 
639 // STATISTICS: example-any
640