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, 2008
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 <fstream>
39
40using namespace Gecode;
41
42/** \brief Order-specifications
43 *
44 * Used in the \ref SteelMill example.
45 *
46 */
47//@{
48typedef int (*order_t)[2]; ///< Type of the order-specification
49extern const int order_weight; ///< Weight-position in order-array elements
50extern const int order_color; ///< Color-position in order-array elements
51//@}
52
53/** \brief Constants for CSPLib instance of the Steel Mill Slab Design Problem.
54 *
55 * Used in the \ref SteelMill example.
56 */
57//@{
58extern int csplib_capacities[]; ///< Capacities
59extern unsigned int csplib_ncapacities; ///< Number of capacities
60extern unsigned int csplib_maxcapacity; ///< Maximum capacity
61extern int csplib_loss[]; ///< Loss for all sizes
62extern int csplib_orders[][2]; ///< Orders
63extern unsigned int csplib_ncolors; ///< Number of colors
64extern unsigned int csplib_norders; ///< Number of orders
65//@}
66
67
68/** \brief %SteelMillOptions for examples with size option and an additional
69 * optional file name parameter.
70 *
71 * Used in the \ref SteelMill example.
72 */
73class SteelMillOptions : public Options {
74private:
75 unsigned int _size; ///< Size value
76 int* _capacities; ///< Capacities
77 int _ncapacities; ///< Number of capacities
78 int _maxcapacity; ///< Maximum capacity
79 int* _loss; ///< Loss for all sizes
80 order_t _orders; ///< Orders
81 int _ncolors; ///< Number of colors
82 unsigned int _norders; ///< Number of orders
83public:
84 /// Initialize options for example with name \a n
85 SteelMillOptions(const char* n)
86 : Options(n), _size(csplib_norders),
87 _capacities(csplib_capacities), _ncapacities(csplib_ncapacities),
88 _maxcapacity(csplib_maxcapacity),
89 _loss(csplib_loss), _orders(&(csplib_orders[0])), _ncolors(csplib_ncolors),
90 _norders(csplib_norders) {}
91 /// Print help text
92 virtual void help(void);
93 /// Parse options from arguments \a argv (number is \a argc)
94 bool parse(int& argc, char* argv[]);
95
96 /// Return size
97 unsigned int size(void) const { return _size; }
98 /// Return capacities
99 int* capacities(void) const { return _capacities; }
100 /// Return number of capacities
101 int ncapacities(void) const { return _ncapacities; }
102 /// Return maximum of capacities
103 int maxcapacity(void) const { return _maxcapacity; }
104 /// Return loss values
105 int* loss(void) const { return _loss; }
106 /// Return orders
107 order_t orders(void) const { return _orders; }
108 /// Return number of colors
109 int ncolors(void) const { return _ncolors; }
110 /// Return number of orders
111 int norders(void) const { return _norders; }
112};
113
114/// Sort orders by weight
115class SortByWeight {
116public:
117 /// The orders
118 order_t orders;
119 /// Initialize orders
120 SortByWeight(order_t _orders) : orders(_orders) {}
121 /// Sort order
122 bool operator() (int i, int j) {
123 // Order i comes before order j if the weight of i is larger than
124 // the weight of j.
125 return (orders[i][order_weight] > orders[j][order_weight]) ||
126 (orders[i][order_weight] == orders[j][order_weight] && i<j);
127 }
128};
129
130/**
131 * \brief %Example: Steel-mill slab design problem
132 *
133 * This model solves the Steel Mill Slab Design Problem (Problem 38 in
134 * <a href="http://csplib.org">CSPLib</a>). The model is from Gargani
135 * and Refalo, "An efficient model and strategy for the steel mill
136 * slab design problem.", CP 2007, except that a decomposition of the
137 * packing constraint is used. The symmetry-breaking search is from
138 * Van Hentenryck and Michel, "The Steel Mill Slab Design Problem
139 * Revisited", CPAIOR 2008.
140 *
141 * The program accepts an optional argument for a data-file containing
142 * an instance of the problem. The format for the data-file is the following:
143 * <pre>
144 * "number of slab capacities" "sequence of capacities in increasing order"
145 * "number of colors"
146 * "number of orders"
147 * "size order 1" "color of order 1"
148 * "size order 2" "color of order 2"
149 * ...
150 * </pre>
151 * Hard instances are available from <a href=
152 * "http://becool.info.ucl.ac.be/steelmillslab">
153 * http://becool.info.ucl.ac.be/steelmillslab</a>.
154 *
155 * \ingroup Example
156 *
157 */
158class SteelMill : public IntMinimizeScript {
159protected:
160 /** \name Instance specification
161 */
162 //@{
163 int* capacities; ///< Capacities
164 int ncapacities; ///< Number of capacities
165 int maxcapacity; ///< Maximum capacity
166 int* loss; ///< Loss for all sizes
167 int ncolors; ///< Number of colors
168 order_t orders; ///< Orders
169 unsigned int norders; ///< Number of orders
170 unsigned int nslabs; ///< Number of slabs
171 //@}
172
173 /** \name Problem variables
174 */
175 //@{
176 IntVarArray slab, ///< Slab assigned to order i
177 slabload, ///< Load of slab j
178 slabcost; ///< Cost of slab j
179 IntVar total_cost; ///< Total cost
180 //@}
181
182public:
183 /// Branching variants
184 enum {
185 SYMMETRY_NONE, ///< Simple symmetry
186 SYMMETRY_BRANCHING, ///< Breaking symmetries with symmetry
187 SYMMETRY_LDSB ///< Use LDSB for symmetry breaking
188 };
189
190 /// Actual model
191 SteelMill(const SteelMillOptions& opt)
192 : // Initialize instance data
193 IntMinimizeScript(opt),
194 capacities(opt.capacities()), ncapacities(opt.ncapacities()),
195 maxcapacity(opt.maxcapacity()), loss(opt.loss()),
196 ncolors(opt.ncolors()), orders(opt.orders()),
197 norders(opt.size()), nslabs(opt.size()),
198 // Initialize problem variables
199 slab(*this, norders, 0,nslabs-1),
200 slabload(*this, nslabs, 0,45),
201 slabcost(*this, nslabs, 0, Int::Limits::max),
202 total_cost(*this, 0, Int::Limits::max)
203 {
204 // Boolean variables for slab[o]==s
205 BoolVarArgs boolslab(norders*nslabs);
206 for (unsigned int i = 0; i < norders; ++i) {
207 BoolVarArgs tmp(nslabs);
208 for (int j = nslabs; j--; ) {
209 boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1);
210 }
211 channel(*this, tmp, slab[i]);
212 }
213
214 // Packing constraints
215 for (unsigned int s = 0; s < nslabs; ++s) {
216 IntArgs c(norders);
217 BoolVarArgs x(norders);
218 for (int i = norders; i--; ) {
219 c[i] = orders[i][order_weight];
220 x[i] = boolslab[s + i*nslabs];
221 }
222 linear(*this, c, x, IRT_EQ, slabload[s]);
223 }
224 // Redundant packing constraint
225 int totalweight = 0;
226 for (unsigned int i = norders; i-- ; )
227 totalweight += orders[i][order_weight] ;
228 linear(*this, slabload, IRT_EQ, totalweight);
229
230
231 // Color constraints
232 IntArgs nofcolor(ncolors);
233 for (int c = ncolors; c--; ) {
234 nofcolor[c] = 0;
235 for (int o = norders; o--; ) {
236 if (orders[o][order_color] == c) nofcolor[c] += 1;
237 }
238 }
239 BoolVar f(*this, 0, 0);
240 for (unsigned int s = 0; s < nslabs; ++s) {
241 BoolVarArgs hascolor(ncolors);
242 for (int c = ncolors; c--; ) {
243 if (nofcolor[c]) {
244 BoolVarArgs hasc(nofcolor[c]);
245 int pos = 0;
246 for (int o = norders; o--; ) {
247 if (orders[o][order_color] == c)
248 hasc[pos++] = boolslab[s + o*nslabs];
249 }
250 assert(pos == nofcolor[c]);
251 hascolor[c] = BoolVar(*this, 0, 1);
252 rel(*this, BOT_OR, hasc, hascolor[c]);
253 } else {
254 hascolor[c] = f;
255 }
256 }
257 linear(*this, hascolor, IRT_LQ, 2);
258 }
259
260 // Compute slabcost
261 IntArgs l(maxcapacity, loss);
262 for (int s = nslabs; s--; ) {
263 element(*this, l, slabload[s], slabcost[s]);
264 }
265 linear(*this, slabcost, IRT_EQ, total_cost);
266
267 // Add branching
268 if (opt.symmetry() == SYMMETRY_BRANCHING) {
269 // Symmetry breaking branching
270 SteelMillBranch::post(*this);
271 } else if (opt.symmetry() == SYMMETRY_NONE) {
272 branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN());
273 } else { // opt.symmetry() == SYMMETRY_LDSB
274 // There is one symmetry: the values (slabs) are interchangeable.
275 Symmetries syms;
276 syms << ValueSymmetry(IntArgs::create(nslabs,0));
277
278 // For variable order we mimic the custom brancher. We use
279 // min-size domain, breaking ties by maximum weight (preferring
280 // to label larger weights earlier). To do this, we first sort
281 // (stably) by maximum weight, then use min-size domain.
282 SortByWeight sbw(orders);
283 IntArgs indices(norders);
284 for (unsigned int i = 0 ; i < norders ; i++)
285 indices[i] = i;
286 Support::quicksort(&indices[0],norders,sbw);
287 IntVarArgs sorted_orders(norders);
288 for (unsigned int i = 0 ; i < norders ; i++) {
289 sorted_orders[i] = slab[indices[i]];
290 }
291 branch(*this, sorted_orders, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
292 }
293 }
294
295 /// Print solution
296 virtual void
297 print(std::ostream& os) const {
298 os << "What slab=" << slab << std::endl;
299 os << "Slab load=" << slabload << std::endl;
300 os << "Slab cost=" << slabcost << std::endl;
301 os << "Total cost=" << total_cost << std::endl;
302 int nslabsused = 0;
303 int nslabscost = 0;
304 bool unassigned = false;
305 for (int i = nslabs; i--; ) {
306 if (!slabload[i].assigned() || !slabcost[i].assigned()) {
307 unassigned = true;
308 break;
309 }
310 if (slabload[i].min()>0) ++nslabsused;
311 if (slabcost[i].min()>0) ++nslabscost;
312 }
313 if (!unassigned)
314 os << "Number of slabs used=" << nslabsused
315 << ", slabs with cost=" << nslabscost
316 << std::endl;
317 os << std::endl;
318 }
319
320 /// Constructor for cloning \a s
321 SteelMill(SteelMill& s)
322 : IntMinimizeScript(s),
323 capacities(s.capacities), ncapacities(s.ncapacities),
324 maxcapacity(s.maxcapacity), loss(s.loss),
325 ncolors(s.ncolors), orders(s.orders),
326 norders(s.norders), nslabs(s.nslabs) {
327 slab.update(*this, s.slab);
328 slabload.update(*this, s.slabload);
329 slabcost.update(*this, s.slabcost);
330 total_cost.update(*this, s.total_cost);
331 }
332 /// Copy during cloning
333 virtual Space*
334 copy(void) {
335 return new SteelMill(*this);
336 }
337 /// Return solution cost
338 virtual IntVar cost(void) const {
339 return total_cost;
340 }
341
342
343 /** \brief Custom brancher for steel mill slab design
344 *
345 * This class implements a custom brancher for SteelMill that
346 * considers all slabs with no order assigned to it currently to be
347 * symmetric.
348 *
349 * \relates SteelMill
350 */
351 class SteelMillBranch : Brancher {
352 protected:
353 /// Cache of first unassigned value
354 mutable int start;
355 /// %Choice
356 class Choice : public Gecode::Choice {
357 public:
358 /// Position of variable
359 int pos;
360 /// Value of variable
361 int val;
362 /** Initialize choice for brancher \a b, number of
363 * alternatives \a a, position \a pos0, and value \a val0.
364 */
365 Choice(const Brancher& b, unsigned int a, int pos0, int val0)
366 : Gecode::Choice(b,a), pos(pos0), val(val0) {}
367 /// Archive into \a e
368 virtual void archive(Archive& e) const {
369 Gecode::Choice::archive(e);
370 e << alternatives() << pos << val;
371 }
372 };
373
374 /// Construct brancher
375 SteelMillBranch(Home home)
376 : Brancher(home), start(0) {}
377 /// Copy constructor
378 SteelMillBranch(Space& home, SteelMillBranch& b)
379 : Brancher(home, b), start(b.start) {
380 }
381
382 public:
383 /// Check status of brancher, return true if alternatives left.
384 virtual bool status(const Space& home) const {
385 const SteelMill& sm = static_cast<const SteelMill&>(home);
386 for (unsigned int i = start; i < sm.norders; ++i)
387 if (!sm.slab[i].assigned()) {
388 start = i;
389 return true;
390 }
391 // No non-assigned orders left
392 return false;
393 }
394 /// Return choice
395 virtual Gecode::Choice* choice(Space& home) {
396 SteelMill& sm = static_cast<SteelMill&>(home);
397 assert(!sm.slab[start].assigned());
398 // Find order with a) minimum size, b) largest weight
399 unsigned int size = sm.norders;
400 int weight = 0;
401 unsigned int pos = start;
402 for (unsigned int i = start; i<sm.norders; ++i) {
403 if (!sm.slab[i].assigned()) {
404 if (sm.slab[i].size() == size &&
405 sm.orders[i][order_weight] > weight) {
406 weight = sm.orders[i][order_weight];
407 pos = i;
408 } else if (sm.slab[i].size() < size) {
409 size = sm.slab[i].size();
410 weight = sm.orders[i][order_weight];
411 pos = i;
412 }
413 }
414 }
415 unsigned int val = sm.slab[pos].min();
416 // Find first still empty slab (all such slabs are symmetric)
417 unsigned int firstzero = 0;
418 while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
419 ++firstzero;
420 assert(pos < sm.nslabs &&
421 val < sm.norders);
422 return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
423 }
424 virtual Choice* choice(const Space&, Archive& e) {
425 unsigned int alt; int pos, val;
426 e >> alt >> pos >> val;
427 return new Choice(*this, alt, pos, val);
428 }
429 /// Perform commit for choice \a _c and alternative \a a
430 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
431 unsigned int a) {
432 SteelMill& sm = static_cast<SteelMill&>(home);
433 const Choice& c = static_cast<const Choice&>(_c);
434 if (a)
435 return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
436 ? ES_FAILED : ES_OK;
437 else
438 return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
439 ? ES_FAILED : ES_OK;
440 }
441 /// Print explanation
442 virtual void print(const Space&, const Gecode::Choice& _c,
443 unsigned int a,
444 std::ostream& o) const {
445 const Choice& c = static_cast<const Choice&>(_c);
446 o << "slab[" << c.pos << "] "
447 << ((a == 0) ? "=" : "!=")
448 << " " << c.val;
449 }
450 /// Copy brancher
451 virtual Actor* copy(Space& home) {
452 return new (home) SteelMillBranch(home, *this);
453 }
454 /// Post brancher
455 static void post(Home home) {
456 (void) new (home) SteelMillBranch(home);
457 }
458 /// Delete brancher and return its size
459 virtual size_t dispose(Space&) {
460 return sizeof(*this);
461 }
462 };
463};
464
465/** \brief Main-function
466 * \relates SteelMill
467 */
468int
469main(int argc, char* argv[]) {
470 SteelMillOptions opt("Steel Mill Slab design");
471 opt.symmetry(SteelMill::SYMMETRY_BRANCHING);
472 opt.symmetry(SteelMill::SYMMETRY_NONE,"none");
473 opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
474 opt.symmetry(SteelMill::SYMMETRY_LDSB,"ldsb");
475 opt.solutions(0);
476 if (!opt.parse(argc,argv))
477 return 1;
478 Script::run<SteelMill,BAB,SteelMillOptions>(opt);
479 return 0;
480}
481
482
483void
484SteelMillOptions::help(void) {
485 Options::help();
486 std::cerr << "\t(string), optional" << std::endl
487 << "\t\tBenchmark to load." << std::endl
488 << "\t\tIf none is given, the standard CSPLib instance is used."
489 << std::endl;
490 std::cerr << "\t(unsigned int), optional" << std::endl
491 << "\t\tNumber of orders to use, in the interval [0..norders]."
492 << std::endl
493 << "\t\tIf none is given, all orders are used." << std::endl;
494}
495
496bool
497SteelMillOptions::parse(int& argc, char* argv[]) {
498 Options::parse(argc,argv);
499 // Check number of arguments
500 if (argc >= 4) {
501 std::cerr << "Too many arguments given, max two allowed (given={";
502 for (int i = 1; i < argc; ++i) {
503 std::cerr << "\"" << argv[i] << "\"";
504 if (i < argc-1) std::cerr << ",";
505 }
506 std::cerr << "})." << std::endl;
507 return false;
508 }
509 // Parse options
510 while (argc >= 2) {
511 bool issize = true;
512 for (int i = strlen(argv[argc-1]); i-- && issize; )
513 issize &= (isdigit(argv[argc-1][i]) != 0);
514 if (issize) {
515 _size = atoi(argv[argc-1]);
516 } else {
517 std::ifstream instance(argv[argc-1]);
518 if (instance.fail()) {
519 std::cerr << "Argument \"" << argv[argc-1]
520 << "\" is neither an integer nor a readable file"
521 << std::endl;
522 return false;
523 }
524 // Read file instance
525 instance >> _ncapacities;
526 _capacities = new int[_ncapacities];
527 _maxcapacity = -1;
528 for (int i = 0; i < _ncapacities; ++i) {
529 instance >> _capacities[i];
530 _maxcapacity = std::max(_maxcapacity, _capacities[i]);
531 }
532 instance >> _ncolors >> _norders;
533 _orders = new int[_norders][2];
534 for (unsigned int i = 0; i < _norders; ++i) {
535 instance >> _orders[i][order_weight] >> _orders[i][order_color];
536 }
537 }
538
539 --argc;
540 }
541 // Compute loss
542 {
543 _loss = new int[_maxcapacity+1];
544 _loss[0] = 0;
545 int currcap = 0;
546 for (int c = 1; c < _maxcapacity; ++c) {
547 if (c > _capacities[currcap]) ++currcap;
548 _loss[c] = _capacities[currcap] - c;
549 }
550 }
551 // Set size, if none given
552 if (_size == 0) {
553 _size = _norders;
554 }
555 // Check size reasonability
556 if (_size == 0 || _size > _norders) {
557 std::cerr << "Size must be between 1 and " << _norders << std::endl;
558 return false;
559 }
560 return true;
561}
562
563// Positions in order array
564const int order_weight = 0;
565const int order_color = 1;
566
567// CSPLib instance
568int csplib_capacities[] =
569 {12, 14, 17, 18, 19,
570 20, 23, 24, 25, 26,
571 27, 28, 29, 30, 32,
572 35, 39, 42, 43, 44};
573unsigned int csplib_ncapacities = 20;
574unsigned int csplib_maxcapacity = 44;
575int csplib_loss[45];
576unsigned int csplib_ncolors = 89;
577unsigned int csplib_norders = 111;
578int csplib_orders[][2] = {
579 {4, 1},
580 {22, 2},
581 {9, 3},
582 {5, 4},
583 {8, 5},
584 {3, 6},
585 {3, 4},
586 {4, 7},
587 {7, 4},
588 {7, 8},
589 {3, 6},
590 {2, 6},
591 {2, 4},
592 {8, 9},
593 {5, 10},
594 {7, 11},
595 {4, 7},
596 {7, 11},
597 {5, 10},
598 {7, 11},
599 {8, 9},
600 {3, 1},
601 {25, 12},
602 {14, 13},
603 {3, 6},
604 {22, 14},
605 {19, 15},
606 {19, 15},
607 {22, 16},
608 {22, 17},
609 {22, 18},
610 {20, 19},
611 {22, 20},
612 {5, 21},
613 {4, 22},
614 {10, 23},
615 {26, 24},
616 {17, 25},
617 {20, 26},
618 {16, 27},
619 {10, 28},
620 {19, 29},
621 {10, 30},
622 {10, 31},
623 {23, 32},
624 {22, 33},
625 {26, 34},
626 {27, 35},
627 {22, 36},
628 {27, 37},
629 {22, 38},
630 {22, 39},
631 {13, 40},
632 {14, 41},
633 {16, 27},
634 {26, 34},
635 {26, 42},
636 {27, 35},
637 {22, 36},
638 {20, 43},
639 {26, 24},
640 {22, 44},
641 {13, 45},
642 {19, 46},
643 {20, 47},
644 {16, 48},
645 {15, 49},
646 {17, 50},
647 {10, 28},
648 {20, 51},
649 {5, 52},
650 {26, 24},
651 {19, 53},
652 {15, 54},
653 {10, 55},
654 {10, 56},
655 {13, 57},
656 {13, 58},
657 {13, 59},
658 {12, 60},
659 {12, 61},
660 {18, 62},
661 {10, 63},
662 {18, 64},
663 {16, 65},
664 {20, 66},
665 {12, 67},
666 {6, 68},
667 {6, 68},
668 {15, 69},
669 {15, 70},
670 {15, 70},
671 {21, 71},
672 {30, 72},
673 {30, 73},
674 {30, 74},
675 {30, 75},
676 {23, 76},
677 {15, 77},
678 {15, 78},
679 {27, 79},
680 {27, 80},
681 {27, 81},
682 {27, 82},
683 {27, 83},
684 {27, 84},
685 {27, 79},
686 {27, 85},
687 {27, 86},
688 {10, 87},
689 {3, 88}
690};
691
692// STATISTICS: example-any