this repo has no description
dekker.one
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38#include <iomanip>
39
40using namespace Gecode;
41
42// Problems
43namespace {
44 // Problem data
45 extern const int* problems[];
46 // Number of problems
47 extern const unsigned int n_problems;
48}
49
50namespace {
51 /**
52 * \brief %Options for car sequencing problems
53 *
54 * \relates CarSequence
55 */
56 class CarOptions : public SizeOptions {
57 private:
58 /// Max slack parameter
59 Driver::UnsignedIntOption _maxstall;
60
61 public:
62 /// Initialize options for example with name \a s
63 CarOptions(const char* s)
64 : SizeOptions(s),
65 _maxstall("maxstall", "Maximum numbere of stalls", 30)
66 {
67 // Add options
68 add(_maxstall);
69 }
70 /// Parse options from arguments \a argv (number is \a argc)
71 void parse(int& argc, char* argv[]) {
72 SizeOptions::parse(argc,argv);
73 }
74 /// Get max stalls
75 int maxstall(void) const { return _maxstall.value(); }
76 };
77
78
79 /**
80 * \brief Propagator that pushes all occurences of a value to the end.
81 *
82 * This propagator uses a variable array \f$x=\langle
83 * x_1,x_2,\ldots,x_n\rangle\f$, a variable \f$y\f$, and a value
84 * \f$val\f$. It It makes sure that the last \f$y\f$ variables of
85 * \f$x\f$ are assigned the value, and that the value does not
86 * appear in the rest of the array. Furthermore, the constriant
87 * ensure that \$fval\$f isnot adjacent to \$fval-1\$f.
88 *
89 * Since the propagator is custom-made for the car sequencing
90 * example, it relies on the fact that the value will be equal to
91 * the upper bound to speed up computation. For example, it can
92 * safely rely on only subscribing to bound events.
93 *
94 * \relates CarSequence
95 */
96 template <class View>
97 class PushToEnd : public NaryOnePropagator<View,Int::PC_INT_BND> {
98 protected:
99 using NaryOnePropagator<View,Int::PC_INT_BND>::x;
100 using NaryOnePropagator<View,Int::PC_INT_BND>::y;
101 int val;
102
103 /// Constructor for cloning \a p
104 PushToEnd(Space& home, PushToEnd& p);
105 /// Constructor for posting
106 PushToEnd(Space& home, ViewArray<View>& x0, View y0, int val0);
107 public:
108 /// Constructor for rewriting \a p during cloning
109 PushToEnd(Space& home, Propagator& p,
110 ViewArray<View>& x0, View y0, int val0);
111 /// Copy propagator during cloning
112 virtual Actor* copy(Space& home);
113 /// Perform propagation
114 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
115 /// Post propagator
116 static ExecStatus post(Space& home,
117 ViewArray<View>& x0, View y0, int val0);
118 };
119
120 template <class View>
121 inline
122 PushToEnd<View>::PushToEnd(Space& home,
123 ViewArray<View>& x0, View y0, int val0)
124 : NaryOnePropagator<View,Int::PC_INT_BND>(home,x0,y0), val(val0) {}
125
126 template <class View>
127 ExecStatus
128 PushToEnd<View>::post(Space& home,
129 ViewArray<View>& x0, View y0, int val0) {
130 (void) new (home) PushToEnd<View>(home,x0,y0,val0);
131 return ES_OK;
132 }
133
134 template <class View>
135 inline
136 PushToEnd<View>::PushToEnd(Space& home, PushToEnd<View>& p)
137 : NaryOnePropagator<View,Int::PC_INT_BND>(home,p), val(p.val) {}
138
139 template <class View>
140 inline
141 PushToEnd<View>::PushToEnd(Space& home, Propagator& p,
142 ViewArray<View>& x0, View y0, int val0)
143 : NaryOnePropagator<View,Int::PC_INT_BND>(home,p,x0,y0), val(val0) {}
144
145 template <class View>
146 Actor*
147 PushToEnd<View>::copy(Space& home) {
148 return new (home) PushToEnd<View>(home,*this);
149 }
150
151 template <class View>
152 ExecStatus
153 PushToEnd<View>::propagate(Space& home, const ModEventDelta&) {
154 // Find number of required positions
155 int min = 0;
156 for (int i = x.size(); i-- && x[i].min() >= val-1; ) {
157 ++min;
158 }
159 // Find number of possible positions
160 int max = 0;
161 {
162 int i = x.size();
163 while (i--) {
164 if (x[i].max() != val) break;
165 ++max;
166 if (max >= y.max()) break;
167 }
168 // No variables later than max can have value val
169 while (i--) {
170 GECODE_ME_CHECK(x[i].le(home, val));
171 }
172 }
173
174 // Constrain y to be in {min..max}
175 GECODE_ME_CHECK(y.gq(home, min));
176 GECODE_ME_CHECK(y.lq(home, max));
177
178 // At least the y.min() last values have value val
179 for (int i = 0, pos = x.size()-1; i < y.min(); ++i, --pos) {
180 GECODE_ME_CHECK(x[pos].eq(home, val));
181 }
182
183 return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
184 }
185
186 /** \brief Post PushToEnd propagator.
187 */
188 void pushtoend(Space& home, IntVarArgs x, IntVar y, int val) {
189 ViewArray<Int::IntView> vx(home, x);
190 Int::IntView vy(y);
191 GECODE_ES_FAIL(PushToEnd<Int::IntView>::post(home, vx, vy, val));
192 }
193
194}
195
196
197/**
198 * \brief %Example: Car sequencing
199 *
200 * See problem 1 at http://www.csplib.org/.
201 *
202 * This model uses extra stall-slots instead of violations, as proposed
203 * in "Combining Forces to Solve the Car Sequencing Problem", Perron
204 * and Shaw, CPAIOR 2004.
205 *
206 * \ingroup Example
207 */
208class CarSequencing : public Script {
209public:
210 /// Branching variants
211 enum {
212 BRANCH_INORDER, ///< Branch from left to right
213 BRANCH_MIDDLE ///< Branch from middle out
214 };
215 /// Propagation variants
216 enum {
217 PROP_REGULAR, ///< Use regular constraints
218 PROP_CUSTOM ///< Use custom constraint
219 };
220protected:
221 /// Problem number
222 const int problem;
223 /// Number of cars
224 const int ncars;
225 /// Number of options
226 const int noptions;
227 /// Number of classes
228 const int nclasses;
229 /// Maximum number of stalls
230 const int maxstall;
231 /// Stall number
232 const int stallval;
233 /// End number
234 const int endval;
235 /// Number of stalls (cost to minimize)
236 IntVar nstall;
237 /// Number of end markers
238 IntVar nend;
239 /// Sequence of cars produced
240 IntVarArray s;
241public:
242 /// Initial model
243 CarSequencing(const CarOptions& opt)
244 : Script(opt),
245 problem(opt.size()),
246 ncars(problems[problem][0]),
247 noptions(problems[problem][1]),
248 nclasses(problems[problem][2]),
249 maxstall(opt.maxstall()),
250 stallval(nclasses),
251 endval(nclasses+1),
252 nstall(*this, 0, maxstall),
253 nend(*this, 0, maxstall),
254 s(*this, ncars+maxstall, 0, nclasses+1)
255 {
256 // Read problem
257 const int* probit = problems[problem] + 3;
258
259 // Sequence requirements for the options.
260 IntArgs max(noptions), block(noptions);
261 for (int i = 0; i < noptions; ++i ) {
262 max[i] = *probit++;
263 }
264 for (int i = 0; i < noptions; ++i ) {
265 block[i] = *probit++;
266 }
267 // Number of cars per class
268 IntArgs ncc(nclasses);
269 // What classes require an option
270 IntSetArgs classes(noptions);
271 int** cdata = new int*[noptions];
272 for (int i = noptions; i--; ) cdata[i] = new int[nclasses];
273 int* n = new int[noptions];
274 for (int i = noptions; i--; ) n[i] = 0;
275 // Read data
276 for (int c = 0; c < nclasses; ++c) {
277 probit++;
278 ncc[c] = *probit++;
279 for (int o = 0; o < noptions; ++o) {
280 if (*probit++) {
281 cdata[o][n[o]++] = c;
282 }
283 }
284 }
285 // Transfer specification data to int-sets
286 for (int o = noptions; o--; ) {
287 classes[o] = IntSet(cdata[o], n[o]);
288 delete [] cdata[o];
289 }
290 delete [] cdata;
291 delete [] n;
292
293 // Count the cars
294 {
295 IntSetArgs c(nclasses+2);
296 for (int i = nclasses; i--; ) {
297 c[i] = IntSet(ncc[i], ncc[i]);
298 }
299 c[stallval] = IntSet(0, maxstall);
300 c[ endval] = IntSet(0, maxstall);
301 count(*this, s, c);
302 }
303
304 // Count number of end and stalls
305 count(*this, s, stallval, IRT_EQ, nstall);
306 count(*this, s, endval, IRT_EQ, nend);
307 rel(*this, nstall+nend == maxstall);
308
309 // Make sure nothing is overloaded
310 IntSet one(1, 1);
311 for (int o = noptions; o--; ) {
312 // sb[i] reflects if car s[i] has option o
313 BoolVarArgs sb(s.size());
314 for (int i = s.size(); i--; ) {
315 BoolVar b(*this, 0, 1);
316 dom(*this, s[i], classes[o], b);
317 sb[i] = b;
318 }
319 sequence(*this, sb, one, block[o], 0, max[o]);
320 }
321
322 // End-markers located at end only
323 switch (opt.propagation()) {
324 case PROP_REGULAR: {
325 IntArgs notend(nclasses), notstallend(nclasses+1);
326 for (int i = nclasses; i--; ) {
327 notend[i] = i;
328 notstallend[i] = i;
329 }
330 notstallend[nclasses] = stallval;
331 REG r = *REG(notend) + REG(notstallend) + *REG(endval);
332 extensional(*this, s, r);
333 for (int pos = s.size()-1, i = 0; i < maxstall; ++i, --pos) {
334 rel(*this, (nend > i) >> (s[pos]==endval));
335 }
336 } break;
337 case PROP_CUSTOM: {
338 pushtoend(*this, s, nend, endval);
339 } break;
340 }
341
342
343 // Branching
344 switch (opt.branching()) {
345 case BRANCH_INORDER:
346 branch(*this, s, INT_VAR_NONE(), INT_VAL_MIN());
347 break;
348 case BRANCH_MIDDLE: {
349 IntVarArgs m(s.size());
350 int mid = s.size() / 2;
351 int pos = 0;
352 m[pos++] = s[mid];
353 for (int i = 1; i <= m.size()/2; ++i) {
354 if (mid-i >= 0)
355 m[pos++] = s[mid-i];
356 if (mid+i < s.size())
357 m[pos++] = s[mid+i];
358 }
359 assert(pos == m.size());
360 branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
361 break;
362 }
363 }
364 }
365
366 /// Return cost
367 virtual void constrain(const Space& _best) {
368 const CarSequencing& best = static_cast<const CarSequencing&>(_best);
369 rel(*this, nstall, IRT_LE, best.nstall.val());
370 }
371
372 /// Print solution
373 virtual void
374 print(std::ostream& os) const {
375 int width = nclasses > 9 ? 2 : 1;
376 const char* space = nclasses > 9 ? " " : "";
377 os << "Stall slots=" << nstall
378 << ", End slots=" << nend << std::endl;
379 int i = 0;
380 for (; i < s.size(); ++i) {
381 if (s[i].assigned()) {
382 int v = s[i].val();
383 if (v == endval) break;
384 if (v == stallval) os << space << "_ ";
385 else os << std::setw(width) << v << " ";
386 } else {
387 os << space << "? ";
388 }
389 if ((i+1)%20 == 0) os << std::endl;
390 }
391 if (i%20)
392 os << std::endl;
393 os << std::endl;
394 }
395
396 /// Constructor for cloning \a s
397 CarSequencing(CarSequencing& cs)
398 : Script(cs),
399 problem(cs.problem),
400 ncars(cs.ncars),
401 noptions(cs.noptions),
402 nclasses(cs.nclasses),
403 maxstall(cs.maxstall),
404 stallval(cs.stallval),
405 endval(cs.endval)
406 {
407 nstall.update(*this, cs.nstall);
408 nend.update(*this, cs.nend);
409 s.update(*this, cs.s);
410 }
411 /// Copy during cloning
412 virtual Space*
413 copy(void) {
414 return new CarSequencing(*this);
415 }
416};
417
418/** \brief Main-function
419 * \relates CarSequencing
420 */
421int
422main(int argc, char* argv[]) {
423 CarOptions opt("CarSequencing");
424 opt.solutions(0);
425 opt.size(0);
426 opt.branching(CarSequencing::BRANCH_INORDER);
427 opt.branching(CarSequencing::BRANCH_INORDER, "inorder");
428 opt.branching(CarSequencing::BRANCH_MIDDLE, "middle");
429 opt.propagation(CarSequencing::PROP_CUSTOM);
430 opt.propagation(CarSequencing::PROP_REGULAR, "regular");
431 opt.propagation(CarSequencing::PROP_CUSTOM, "custom");
432 opt.parse(argc,argv);
433 if (opt.size() >= n_problems) {
434 std::cerr << "Error: size must be between 0 and "
435 << n_problems-1 << std::endl;
436 return 1;
437 }
438
439 Script::run<CarSequencing,BAB,CarOptions>(opt);
440 return 0;
441}
442
443
444namespace {
445 /// Problems from CSPLib
446
447 /// Simple initial example
448 const int p0[] = {
449 10, 5, 6,
450 1, 2, 1, 2, 1,
451 2, 3, 3, 5, 5,
452 0, 1, 1, 0, 1, 1, 0,
453 1, 1, 0, 0, 0, 1, 0,
454 2, 2, 0, 1, 0, 0, 1,
455 3, 2, 0, 1, 0, 1, 0,
456 4, 2, 1, 0, 1, 0, 0,
457 5, 2, 1, 1, 0, 0, 0
458 };
459
460 // ---------------------------------
461 // Problem 4/72 (Regin & Puget // 1)
462 // ---------------------------------
463 const int p1[] = {
464 100, 5, 22,
465 1, 2, 1, 2, 1,
466 2, 3, 3, 5, 5,
467 0, 6, 1, 0, 0, 1, 0,
468 1, 10, 1, 1, 1, 0, 0,
469 2, 2, 1, 1, 0, 0, 1,
470 3, 2, 0, 1, 1, 0, 0,
471 4, 8, 0, 0, 0, 1, 0,
472 5, 15, 0, 1, 0, 0, 0,
473 6, 1, 0, 1, 1, 1, 0,
474 7, 5, 0, 0, 1, 1, 0,
475 8, 2, 1, 0, 1, 1, 0,
476 9, 3, 0, 0, 1, 0, 0,
477 10, 2, 1, 0, 1, 0, 0,
478 11, 1, 1, 1, 1, 0, 1,
479 12, 8, 0, 1, 0, 1, 0,
480 13, 3, 1, 0, 0, 1, 1,
481 14, 10, 1, 0, 0, 0, 0,
482 15, 4, 0, 1, 0, 0, 1,
483 16, 4, 0, 0, 0, 0, 1,
484 17, 2, 1, 0, 0, 0, 1,
485 18, 4, 1, 1, 0, 0, 0,
486 19, 6, 1, 1, 0, 1, 0,
487 20, 1, 1, 0, 1, 0, 1,
488 21, 1, 1, 1, 1, 1, 1,
489 };
490
491 // --------------------------------
492 // Problem 6/76, (Regin & Puget // 2)
493 // --------------------------------
494 const int p2[] = {
495 100, 5, 22,
496 1, 2, 1, 2, 1,
497 2, 3, 3, 5, 5,
498 0, 13, 1, 0, 0, 0, 0,
499 1, 8, 0, 0, 0, 1, 0,
500 2, 7, 0, 1, 0, 0, 0,
501 3, 1, 1, 0, 0, 1, 0,
502 4, 12, 0, 0, 1, 0, 0,
503 5, 5, 0, 1, 0, 1, 0,
504 6, 5, 0, 0, 1, 1, 0,
505 7, 6, 0, 1, 1, 0, 0,
506 8, 3, 1, 0, 0, 0, 1,
507 9, 12, 1, 1, 0, 0, 0,
508 10, 8, 1, 1, 0, 1, 0,
509 11, 2, 1, 0, 0, 1, 1,
510 12, 2, 1, 1, 1, 0, 0,
511 13, 1, 0, 1, 0, 1, 1,
512 14, 4, 1, 0, 1, 0, 0,
513 15, 4, 0, 1, 0, 0, 1,
514 16, 1, 1, 1, 0, 1, 1,
515 17, 2, 1, 0, 1, 1, 0,
516 18, 1, 0, 0, 0, 0, 1,
517 19, 1, 1, 1, 1, 1, 0,
518 20, 1, 1, 1, 0, 0, 1,
519 21, 1, 0, 1, 1, 1, 0,
520 };
521
522 // ---------------------------------
523 // Problem 10/93, (Regin & Puget // 3)
524 // ---------------------------------
525 const int p3[] = {
526 100, 5, 25,
527 1, 2, 1, 2, 1,
528 2, 3, 3, 5, 5,
529 0, 7, 1, 0, 0, 1, 0,
530 1, 11, 1, 1, 0, 0, 0,
531 2, 1, 0, 1, 1, 1, 1,
532 3, 3, 1, 0, 1, 0, 0,
533 4, 15, 0, 1, 0, 0, 0,
534 5, 2, 1, 0, 1, 1, 0,
535 6, 8, 0, 1, 0, 1, 0,
536 7, 5, 0, 0, 1, 0, 0,
537 8, 3, 0, 0, 0, 1, 0,
538 9, 4, 0, 1, 1, 1, 0,
539 10, 5, 1, 0, 0, 0, 0,
540 11, 2, 1, 1, 1, 0, 1,
541 12, 6, 0, 1, 1, 0, 0,
542 13, 2, 0, 0, 1, 0, 1,
543 14, 2, 0, 1, 0, 0, 1,
544 15, 4, 1, 1, 1, 1, 0,
545 16, 3, 1, 0, 0, 0, 1,
546 17, 5, 1, 1, 0, 1, 0,
547 18, 2, 1, 1, 1, 0, 0,
548 19, 4, 1, 1, 0, 0, 1,
549 20, 1, 1, 0, 0, 1, 1,
550 21, 1, 1, 1, 0, 1, 1,
551 22, 1, 0, 1, 0, 1, 1,
552 23, 1, 0, 1, 1, 0, 1,
553 24, 2, 0, 0, 0, 0, 1,
554 };
555
556 // --------------
557 // Problem 16/81,
558 // --------------
559 const int p4[] = {
560 100, 5, 26,
561 1, 2, 1, 2, 1,
562 2, 3, 3, 5, 5,
563 0, 10, 1, 0, 0, 0, 0,
564 1, 2, 0, 0, 0, 0, 1,
565 2, 8, 0, 1, 0, 1, 0,
566 3, 8, 0, 0, 0, 1, 0,
567 4, 6, 0, 1, 1, 0, 0,
568 5, 11, 0, 1, 0, 0, 0,
569 6, 3, 0, 0, 1, 0, 0,
570 7, 2, 0, 0, 1, 1, 0,
571 8, 7, 1, 1, 0, 0, 0,
572 9, 2, 1, 0, 0, 1, 1,
573 10, 4, 1, 0, 1, 0, 0,
574 11, 7, 1, 0, 0, 1, 0,
575 12, 1, 1, 1, 1, 0, 1,
576 13, 3, 0, 1, 1, 1, 0,
577 14, 4, 0, 1, 0, 0, 1,
578 15, 5, 1, 1, 1, 0, 0,
579 16, 2, 1, 1, 0, 0, 1,
580 17, 1, 1, 0, 1, 1, 1,
581 18, 2, 1, 0, 1, 1, 0,
582 19, 3, 1, 0, 0, 0, 1,
583 20, 2, 0, 1, 1, 0, 1,
584 21, 1, 0, 1, 0, 1, 1,
585 22, 3, 1, 1, 0, 1, 0,
586 23, 1, 0, 0, 1, 1, 1,
587 24, 1, 1, 1, 1, 1, 1,
588 25, 1, 1, 1, 1, 1, 0,
589 };
590
591 // ----------------------------------
592 // Problem 19/71, (Regin & Puget // 4)
593 // ----------------------------------
594 const int p5[] = {
595 100, 5, 23,
596 1, 2, 1, 2, 1,
597 2, 3, 3, 5, 5,
598 0, 2, 0, 0, 0, 1, 1,
599 1, 2, 0, 0, 1, 0, 1,
600 2, 5, 0, 1, 1, 1, 0,
601 3, 4, 0, 0, 0, 1, 0,
602 4, 4, 0, 1, 0, 1, 0,
603 5, 1, 1, 1, 0, 0, 1,
604 6, 3, 1, 1, 1, 0, 1,
605 7, 4, 0, 0, 1, 0, 0,
606 8, 19, 0, 1, 0, 0, 0,
607 9, 7, 1, 1, 0, 1, 0,
608 10, 10, 1, 0, 0, 0, 0,
609 11, 1, 0, 0, 1, 1, 0,
610 12, 5, 1, 1, 1, 1, 0,
611 13, 2, 1, 0, 1, 1, 0,
612 14, 6, 1, 1, 0, 0, 0,
613 15, 4, 1, 1, 1, 0, 0,
614 16, 8, 1, 0, 0, 1, 0,
615 17, 1, 1, 0, 0, 0, 1,
616 18, 4, 0, 1, 1, 0, 0,
617 19, 2, 0, 0, 0, 0, 1,
618 20, 4, 0, 1, 0, 0, 1,
619 21, 1, 1, 1, 0, 1, 1,
620 22, 1, 0, 1, 1, 0, 1,
621 };
622
623 const int* problems[] = {
624 &p0[0],
625 &p1[0],
626 &p2[0],
627 &p3[0],
628 &p4[0],
629 &p5[0],
630 };
631
632 /// The number of instances
633 const unsigned int n_problems = sizeof(problems)/sizeof(int*);
634};
635
636// STATISTICS: example-any
637