Generated on Fri Aug 24 2012 04:52:12 for Gecode by doxygen 1.8.1.1
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: 2011-09-19 22:02:26 +1000 (Mon, 19 Sep 2011) $ by $Author: schulte $
11  * $Revision: 12400 $
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
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  };
225  enum {
228  };
229 protected:
231  const int problem;
233  const int ncars;
235  const int noptions;
237  const int nclasses;
239  const int maxstall;
241  const int stallval;
243  const int endval;
250 public:
252  CarSequencing(const CarOptions& opt)
253  : problem(opt.size()),
254  ncars(problems[problem][0]),
255  noptions(problems[problem][1]),
256  nclasses(problems[problem][2]),
257  maxstall(opt.maxstall()),
259  endval(nclasses+1),
260  nstall(*this, 0, maxstall),
261  nend(*this, 0, maxstall),
262  s(*this, ncars+maxstall, 0, nclasses+1)
263  {
264  // Read problem
265  const int* probit = problems[problem] + 3;
266 
267  // Sequence requirements for the options.
268  IntArgs max(noptions), block(noptions);
269  for (int i = 0; i < noptions; ++i ) {
270  max[i] = *probit++;
271  }
272  for (int i = 0; i < noptions; ++i ) {
273  block[i] = *probit++;
274  }
275  // Number of cars per class
276  IntArgs ncc(nclasses);
277  // What classes require an option
278  IntSetArgs classes(noptions);
279  int** cdata = new int*[noptions];
280  for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
281  int* n = new int[noptions];
282  for (int i = noptions; i--; ) n[i] = 0;
283  // Read data
284  for (int c = 0; c < nclasses; ++c) {
285  *probit++;
286  ncc[c] = *probit++;
287  for (int o = 0; o < noptions; ++o) {
288  if (*probit++) {
289  cdata[o][n[o]++] = c;
290  }
291  }
292  }
293  // Transfer specification data to int-sets
294  for (int o = noptions; o--; ) {
295  classes[o] = IntSet(cdata[o], n[o]);
296  delete [] cdata[o];
297  }
298  delete [] cdata;
299  delete [] n;
300 
301  // Count the cars
302  {
303  IntSetArgs c(nclasses+2);
304  for (int i = nclasses; i--; ) {
305  c[i] = IntSet(ncc[i], ncc[i]);
306  }
307  c[stallval] = IntSet(0, maxstall);
308  c[ endval] = IntSet(0, maxstall);
309  count(*this, s, c);
310  }
311 
312  // Count number of end and stalls
313  count(*this, s, stallval, IRT_EQ, nstall);
314  count(*this, s, endval, IRT_EQ, nend);
315  rel(*this, nstall+nend == maxstall);
316 
317  // Make sure nothing is overloaded
318  IntSet one(1, 1);
319  for (int o = noptions; o--; ) {
320  // sb[i] reflects if car s[i] has option o
321  BoolVarArgs sb(s.size());
322  for (int i = s.size(); i--; ) {
323  BoolVar b(*this, 0, 1);
324  dom(*this, s[i], classes[o], b);
325  sb[i] = b;
326  }
327  sequence(*this, sb, one, block[o], 0, max[o]);
328  }
329 
330  // End-markers located at end only
331  switch (opt.propagation()) {
332  case PROP_REGULAR: {
333  IntArgs notend(nclasses), notstallend(nclasses+1);
334  for (int i = nclasses; i--; ) {
335  notend[i] = i;
336  notstallend[i] = i;
337  }
338  notstallend[nclasses] = stallval;
339  REG r = *REG(notend) + REG(notstallend) + *REG(endval);
340  extensional(*this, s, r);
341  for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
342  rel(*this, (nend > i) >> (s[pos]==endval));
343  }
344  } break;
345  case PROP_CUSTOM: {
346  pushtoend(*this, s, nend, endval);
347  } break;
348  }
349 
350 
351  // Branching
352  switch (opt.branching()) {
353  case BRANCH_INORDER:
354  branch(*this, s, INT_VAR_NONE, INT_VAL_MIN);
355  break;
356  case BRANCH_MIDDLE: {
357  IntVarArgs m(s.size());
358  int mid = s.size() / 2;
359  int pos = 0;
360  m[pos++] = s[mid];
361  for (int i = 1; i <= m.size()/2; ++i) {
362  if (mid-i >= 0)
363  m[pos++] = s[mid-i];
364  if (mid+i < s.size())
365  m[pos++] = s[mid+i];
366  }
367  assert(pos == m.size());
368  branch(*this, m, INT_VAR_NONE, INT_VAL_MIN);
369  break;
370  }
371  }
372  }
373 
375  virtual void constrain(const Space& _best) {
376  const CarSequencing& best = static_cast<const CarSequencing&>(_best);
377  rel(*this, nstall, IRT_LE, best.nstall.val());
378  }
379 
381  virtual void
382  print(std::ostream& os) const {
383  int width = nclasses > 9 ? 2 : 1;
384  const char* space = nclasses > 9 ? " " : "";
385  os << "Stall slots=" << nstall
386  << ", End slots=" << nend << std::endl;
387  int i = 0;
388  for (; i < s.size(); ++i) {
389  if (s[i].assigned()) {
390  int v = s[i].val();
391  if (v == endval) break;
392  if (v == stallval) os << space << "_ ";
393  else os << std::setw(width) << v << " ";
394  } else {
395  os << space << "? ";
396  }
397  if ((i+1)%20 == 0) os << std::endl;
398  }
399  if (i%20)
400  os << std::endl;
401  os << std::endl;
402  }
403 
405  CarSequencing(bool share, CarSequencing& cs)
406  : Script(share,cs),
407  problem(cs.problem),
408  ncars(cs.ncars),
409  noptions(cs.noptions),
410  nclasses(cs.nclasses),
411  maxstall(cs.maxstall),
412  stallval(cs.stallval),
413  endval(cs.endval)
414  {
415  nstall.update(*this, share, cs.nstall);
416  nend.update(*this, share, cs.nend);
417  s.update(*this, share, cs.s);
418  }
420  virtual Space*
421  copy(bool share) {
422  return new CarSequencing(share,*this);
423  }
424 };
425 
429 int
430 main(int argc, char* argv[]) {
431  CarOptions opt("CarSequencing");
432  opt.solutions(0);
433  opt.size(0);
434  opt.search(CarSequencing::SEARCH_BAB);
435  opt.search(CarSequencing::SEARCH_BAB, "bab");
436  opt.search(CarSequencing::SEARCH_RESTART, "restart");
437  opt.branching(CarSequencing::BRANCH_INORDER);
438  opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
439  opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
440  opt.propagation(CarSequencing::PROP_CUSTOM);
441  opt.propagation(CarSequencing::PROP_REGULAR, "regular");
442  opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
443  opt.parse(argc,argv);
444  if (opt.size() >= n_problems) {
445  std::cerr << "Error: size must be between 0 and "
446  << n_problems-1 << std::endl;
447  return 1;
448  }
449 
450  switch (opt.search()) {
452  Script::run<CarSequencing,BAB,CarOptions>(opt); break;
454  Script::run<CarSequencing,Restart,CarOptions>(opt); break;
455  }
456  return 0;
457 }
458 
459 
460 namespace {
462 
464  const int p0[] = {
465  10, 5, 6,
466  1, 2, 1, 2, 1,
467  2, 3, 3, 5, 5,
468  0, 1, 1, 0, 1, 1, 0,
469  1, 1, 0, 0, 0, 1, 0,
470  2, 2, 0, 1, 0, 0, 1,
471  3, 2, 0, 1, 0, 1, 0,
472  4, 2, 1, 0, 1, 0, 0,
473  5, 2, 1, 1, 0, 0, 0
474  };
475 
476  // ---------------------------------
477  // Problem 4/72 (Regin & Puget // 1)
478  // ---------------------------------
479  const int p1[] = {
480  100, 5, 22,
481  1, 2, 1, 2, 1,
482  2, 3, 3, 5, 5,
483  0, 6, 1, 0, 0, 1, 0,
484  1, 10, 1, 1, 1, 0, 0,
485  2, 2, 1, 1, 0, 0, 1,
486  3, 2, 0, 1, 1, 0, 0,
487  4, 8, 0, 0, 0, 1, 0,
488  5, 15, 0, 1, 0, 0, 0,
489  6, 1, 0, 1, 1, 1, 0,
490  7, 5, 0, 0, 1, 1, 0,
491  8, 2, 1, 0, 1, 1, 0,
492  9, 3, 0, 0, 1, 0, 0,
493  10, 2, 1, 0, 1, 0, 0,
494  11, 1, 1, 1, 1, 0, 1,
495  12, 8, 0, 1, 0, 1, 0,
496  13, 3, 1, 0, 0, 1, 1,
497  14, 10, 1, 0, 0, 0, 0,
498  15, 4, 0, 1, 0, 0, 1,
499  16, 4, 0, 0, 0, 0, 1,
500  17, 2, 1, 0, 0, 0, 1,
501  18, 4, 1, 1, 0, 0, 0,
502  19, 6, 1, 1, 0, 1, 0,
503  20, 1, 1, 0, 1, 0, 1,
504  21, 1, 1, 1, 1, 1, 1,
505  };
506 
507  // --------------------------------
508  // Problem 6/76, (Regin & Puget // 2)
509  // --------------------------------
510  const int p2[] = {
511  100, 5, 22,
512  1, 2, 1, 2, 1,
513  2, 3, 3, 5, 5,
514  0, 13, 1, 0, 0, 0, 0,
515  1, 8, 0, 0, 0, 1, 0,
516  2, 7, 0, 1, 0, 0, 0,
517  3, 1, 1, 0, 0, 1, 0,
518  4, 12, 0, 0, 1, 0, 0,
519  5, 5, 0, 1, 0, 1, 0,
520  6, 5, 0, 0, 1, 1, 0,
521  7, 6, 0, 1, 1, 0, 0,
522  8, 3, 1, 0, 0, 0, 1,
523  9, 12, 1, 1, 0, 0, 0,
524  10, 8, 1, 1, 0, 1, 0,
525  11, 2, 1, 0, 0, 1, 1,
526  12, 2, 1, 1, 1, 0, 0,
527  13, 1, 0, 1, 0, 1, 1,
528  14, 4, 1, 0, 1, 0, 0,
529  15, 4, 0, 1, 0, 0, 1,
530  16, 1, 1, 1, 0, 1, 1,
531  17, 2, 1, 0, 1, 1, 0,
532  18, 1, 0, 0, 0, 0, 1,
533  19, 1, 1, 1, 1, 1, 0,
534  20, 1, 1, 1, 0, 0, 1,
535  21, 1, 0, 1, 1, 1, 0,
536  };
537 
538  // ---------------------------------
539  // Problem 10/93, (Regin & Puget // 3)
540  // ---------------------------------
541  const int p3[] = {
542  100, 5, 25,
543  1, 2, 1, 2, 1,
544  2, 3, 3, 5, 5,
545  0, 7, 1, 0, 0, 1, 0,
546  1, 11, 1, 1, 0, 0, 0,
547  2, 1, 0, 1, 1, 1, 1,
548  3, 3, 1, 0, 1, 0, 0,
549  4, 15, 0, 1, 0, 0, 0,
550  5, 2, 1, 0, 1, 1, 0,
551  6, 8, 0, 1, 0, 1, 0,
552  7, 5, 0, 0, 1, 0, 0,
553  8, 3, 0, 0, 0, 1, 0,
554  9, 4, 0, 1, 1, 1, 0,
555  10, 5, 1, 0, 0, 0, 0,
556  11, 2, 1, 1, 1, 0, 1,
557  12, 6, 0, 1, 1, 0, 0,
558  13, 2, 0, 0, 1, 0, 1,
559  14, 2, 0, 1, 0, 0, 1,
560  15, 4, 1, 1, 1, 1, 0,
561  16, 3, 1, 0, 0, 0, 1,
562  17, 5, 1, 1, 0, 1, 0,
563  18, 2, 1, 1, 1, 0, 0,
564  19, 4, 1, 1, 0, 0, 1,
565  20, 1, 1, 0, 0, 1, 1,
566  21, 1, 1, 1, 0, 1, 1,
567  22, 1, 0, 1, 0, 1, 1,
568  23, 1, 0, 1, 1, 0, 1,
569  24, 2, 0, 0, 0, 0, 1,
570  };
571 
572  // --------------
573  // Problem 16/81,
574  // --------------
575  const int p4[] = {
576  100, 5, 26,
577  1, 2, 1, 2, 1,
578  2, 3, 3, 5, 5,
579  0, 10, 1, 0, 0, 0, 0,
580  1, 2, 0, 0, 0, 0, 1,
581  2, 8, 0, 1, 0, 1, 0,
582  3, 8, 0, 0, 0, 1, 0,
583  4, 6, 0, 1, 1, 0, 0,
584  5, 11, 0, 1, 0, 0, 0,
585  6, 3, 0, 0, 1, 0, 0,
586  7, 2, 0, 0, 1, 1, 0,
587  8, 7, 1, 1, 0, 0, 0,
588  9, 2, 1, 0, 0, 1, 1,
589  10, 4, 1, 0, 1, 0, 0,
590  11, 7, 1, 0, 0, 1, 0,
591  12, 1, 1, 1, 1, 0, 1,
592  13, 3, 0, 1, 1, 1, 0,
593  14, 4, 0, 1, 0, 0, 1,
594  15, 5, 1, 1, 1, 0, 0,
595  16, 2, 1, 1, 0, 0, 1,
596  17, 1, 1, 0, 1, 1, 1,
597  18, 2, 1, 0, 1, 1, 0,
598  19, 3, 1, 0, 0, 0, 1,
599  20, 2, 0, 1, 1, 0, 1,
600  21, 1, 0, 1, 0, 1, 1,
601  22, 3, 1, 1, 0, 1, 0,
602  23, 1, 0, 0, 1, 1, 1,
603  24, 1, 1, 1, 1, 1, 1,
604  25, 1, 1, 1, 1, 1, 0,
605  };
606 
607  // ----------------------------------
608  // Problem 19/71, (Regin & Puget // 4)
609  // ----------------------------------
610  const int p5[] = {
611  100, 5, 23,
612  1, 2, 1, 2, 1,
613  2, 3, 3, 5, 5,
614  0, 2, 0, 0, 0, 1, 1,
615  1, 2, 0, 0, 1, 0, 1,
616  2, 5, 0, 1, 1, 1, 0,
617  3, 4, 0, 0, 0, 1, 0,
618  4, 4, 0, 1, 0, 1, 0,
619  5, 1, 1, 1, 0, 0, 1,
620  6, 3, 1, 1, 1, 0, 1,
621  7, 4, 0, 0, 1, 0, 0,
622  8, 19, 0, 1, 0, 0, 0,
623  9, 7, 1, 1, 0, 1, 0,
624  10, 10, 1, 0, 0, 0, 0,
625  11, 1, 0, 0, 1, 1, 0,
626  12, 5, 1, 1, 1, 1, 0,
627  13, 2, 1, 0, 1, 1, 0,
628  14, 6, 1, 1, 0, 0, 0,
629  15, 4, 1, 1, 1, 0, 0,
630  16, 8, 1, 0, 0, 1, 0,
631  17, 1, 1, 0, 0, 0, 1,
632  18, 4, 0, 1, 1, 0, 0,
633  19, 2, 0, 0, 0, 0, 1,
634  20, 4, 0, 1, 0, 0, 1,
635  21, 1, 1, 1, 0, 1, 1,
636  22, 1, 0, 1, 1, 0, 1,
637  };
638 
639  const int* problems[] = {
640  &p0[0],
641  &p1[0],
642  &p2[0],
643  &p3[0],
644  &p4[0],
645  &p5[0],
646  };
647 
649  const unsigned int n_problems = sizeof(problems)/sizeof(int*);
650 };
651 
652 // STATISTICS: example-any
653