Generated on Sat May 25 2013 18:00:32 for Gecode by doxygen 1.8.3.1
steel-mill.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, 2008
8  *
9  * Last modified:
10  * $Date: 2013-03-11 14:47:11 +0100 (Mon, 11 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13490 $
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 <fstream>
43 
44 using namespace Gecode;
45 
52 typedef int (*order_t)[2];
53 extern const int order_weight;
54 extern const int order_color;
55 
56 
62 extern int csplib_capacities[];
63 extern unsigned int csplib_ncapacities;
64 extern unsigned int csplib_maxcapacity;
65 extern int csplib_loss[];
66 extern int csplib_orders[][2];
67 extern unsigned int csplib_ncolors;
68 extern unsigned int csplib_norders;
69 
70 
71 
77 class SteelMillOptions : public Options {
78 private:
79  unsigned int _size;
80  int* _capacities;
81  int _ncapacities;
82  int _maxcapacity;
83  int* _loss;
84  order_t _orders;
85  int _ncolors;
86  unsigned int _norders;
87 public:
89  SteelMillOptions(const char* n)
90  : Options(n), _size(csplib_norders),
91  _capacities(csplib_capacities), _ncapacities(csplib_ncapacities),
92  _maxcapacity(csplib_maxcapacity),
93  _loss(csplib_loss), _orders(&(csplib_orders[0])), _ncolors(csplib_ncolors),
94  _norders(csplib_norders) {}
96  virtual void help(void);
98  bool parse(int& argc, char* argv[]);
99 
101  unsigned int size(void) const { return _size; }
103  int* capacities(void) const { return _capacities; }
105  int ncapacities(void) const { return _ncapacities; }
107  int maxcapacity(void) const { return _maxcapacity; }
109  int* loss(void) const { return _loss; }
111  order_t orders(void) const { return _orders; }
113  int ncolors(void) const { return _ncolors; }
115  int norders(void) const { return _norders; }
116 };
117 
120 public:
124  SortByWeight(order_t _orders) : orders(_orders) {}
126  bool operator() (int i, int j) {
127  // Order i comes before order j if the weight of i is larger than
128  // the weight of j.
129  return (orders[i][order_weight] > orders[j][order_weight]) ||
130  (orders[i][order_weight] == orders[j][order_weight] && i<j);
131  }
132 };
133 
162 class SteelMill : public MinimizeScript {
163 protected:
167  int* capacities;
170  int* loss;
171  int ncolors;
173  unsigned int norders;
174  unsigned int nslabs;
175 
176 
180  IntVarArray slab,
181  slabload,
182  slabcost;
184 
185 
186 public:
188  enum {
191  SYMMETRY_LDSB
192  };
193 
196  : // Initialize instance data
197  capacities(opt.capacities()), ncapacities(opt.ncapacities()),
198  maxcapacity(opt.maxcapacity()), loss(opt.loss()),
199  ncolors(opt.ncolors()), orders(opt.orders()),
200  norders(opt.size()), nslabs(opt.size()),
201  // Initialize problem variables
202  slab(*this, norders, 0,nslabs-1),
203  slabload(*this, nslabs, 0,45),
204  slabcost(*this, nslabs, 0, Int::Limits::max),
205  total_cost(*this, 0, Int::Limits::max)
206  {
207  // Boolean variables for slab[o]==s
208  BoolVarArgs boolslab(norders*nslabs);
209  for (unsigned int i = 0; i < norders; ++i) {
210  BoolVarArgs tmp(nslabs);
211  for (int j = nslabs; j--; ) {
212  boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1);
213  }
214  channel(*this, tmp, slab[i]);
215  }
216 
217  // Packing constraints
218  for (unsigned int s = 0; s < nslabs; ++s) {
219  IntArgs c(norders);
220  BoolVarArgs x(norders);
221  for (int i = norders; i--; ) {
222  c[i] = orders[i][order_weight];
223  x[i] = boolslab[s + i*nslabs];
224  }
225  linear(*this, c, x, IRT_EQ, slabload[s]);
226  }
227  // Redundant packing constraint
228  int totalweight = 0;
229  for (unsigned int i = norders; i-- ; )
230  totalweight += orders[i][order_weight] ;
231  linear(*this, slabload, IRT_EQ, totalweight);
232 
233 
234  // Color constraints
235  IntArgs nofcolor(ncolors);
236  for (int c = ncolors; c--; ) {
237  nofcolor[c] = 0;
238  for (int o = norders; o--; ) {
239  if (orders[o][order_color] == c) nofcolor[c] += 1;
240  }
241  }
242  BoolVar f(*this, 0, 0);
243  for (unsigned int s = 0; s < nslabs; ++s) {
244  BoolVarArgs hascolor(ncolors);
245  for (int c = ncolors; c--; ) {
246  if (nofcolor[c]) {
247  BoolVarArgs hasc(nofcolor[c]);
248  int pos = 0;
249  for (int o = norders; o--; ) {
250  if (orders[o][order_color] == c)
251  hasc[pos++] = boolslab[s + o*nslabs];
252  }
253  assert(pos == nofcolor[c]);
254  hascolor[c] = BoolVar(*this, 0, 1);
255  rel(*this, BOT_OR, hasc, hascolor[c]);
256  } else {
257  hascolor[c] = f;
258  }
259  }
260  linear(*this, hascolor, IRT_LQ, 2);
261  }
262 
263  // Compute slabcost
264  IntArgs l(maxcapacity, loss);
265  for (int s = nslabs; s--; ) {
266  element(*this, l, slabload[s], slabcost[s]);
267  }
268  linear(*this, slabcost, IRT_EQ, total_cost);
269 
270  // Add branching
271  if (opt.symmetry() == SYMMETRY_BRANCHING) {
272  // Symmetry breaking branching
273  SteelMillBranch::post(*this);
274  } else if (opt.symmetry() == SYMMETRY_NONE) {
275  branch(*this, slab, INT_VAR_MAX_MIN(), INT_VAL_MIN());
276  } else { // opt.symmetry() == SYMMETRY_LDSB
277  // There is one symmetry: the values (slabs) are interchangeable.
278  Symmetries syms;
279  syms << ValueSymmetry(IntArgs::create(nslabs,0));
280 
281  // For variable order we mimic the custom brancher. We use
282  // min-size domain, breaking ties by maximum weight (preferring
283  // to label larger weights earlier). To do this, we first sort
284  // (stably) by maximum weight, then use min-size domain.
285  SortByWeight sbw(orders);
286  IntArgs indices(norders);
287  for (unsigned int i = 0 ; i < norders ; i++)
288  indices[i] = i;
289  Support::quicksort(&indices[0],norders,sbw);
290  IntVarArgs sorted_orders(norders);
291  for (unsigned int i = 0 ; i < norders ; i++) {
292  sorted_orders[i] = slab[indices[i]];
293  }
294  branch(*this, sorted_orders, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
295  }
296  }
297 
299  virtual void
300  print(std::ostream& os) const {
301  os << "What slab=" << slab << std::endl;
302  os << "Slab load=" << slabload << std::endl;
303  os << "Slab cost=" << slabcost << std::endl;
304  os << "Total cost=" << total_cost << std::endl;
305  int nslabsused = 0;
306  int nslabscost = 0;
307  bool unassigned = false;
308  for (int i = nslabs; i--; ) {
309  if (!slabload[i].assigned() || !slabcost[i].assigned()) {
310  unassigned = true;
311  break;
312  }
313  if (slabload[i].min()>0) ++nslabsused;
314  if (slabcost[i].min()>0) ++nslabscost;
315  }
316  if (!unassigned)
317  os << "Number of slabs used=" << nslabsused
318  << ", slabs with cost=" << nslabscost
319  << std::endl;
320  os << std::endl;
321  }
322 
324  SteelMill(bool share, SteelMill& s)
325  : MinimizeScript(share,s),
326  capacities(s.capacities), ncapacities(s.ncapacities),
327  maxcapacity(s.maxcapacity), loss(s.loss),
328  ncolors(s.ncolors), orders(s.orders),
329  norders(s.norders), nslabs(s.nslabs) {
330  slab.update(*this, share, s.slab);
331  slabload.update(*this, share, s.slabload);
332  slabcost.update(*this, share, s.slabcost);
333  total_cost.update(*this, share, s.total_cost);
334  }
336  virtual Space*
337  copy(bool share) {
338  return new SteelMill(share,*this);
339  }
341  virtual IntVar cost(void) const {
342  return total_cost;
343  }
344 
345 
355  protected:
357  mutable int start;
359  class Choice : public Gecode::Choice {
360  public:
362  int pos;
364  int val;
368  Choice(const Brancher& b, unsigned int a, int pos0, int val0)
369  : Gecode::Choice(b,a), pos(pos0), val(val0) {}
371  virtual size_t size(void) const {
372  return sizeof(Choice);
373  }
375  virtual void archive(Archive& e) const {
377  e << alternatives() << pos << val;
378  }
379  };
380 
383  : Brancher(home), start(0) {}
385  SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
386  : Brancher(home, share, b), start(b.start) {
387  }
388 
389  public:
391  virtual bool status(const Space& home) const {
392  const SteelMill& sm = static_cast<const SteelMill&>(home);
393  for (unsigned int i = start; i < sm.norders; ++i)
394  if (!sm.slab[i].assigned()) {
395  start = i;
396  return true;
397  }
398  // No non-assigned orders left
399  return false;
400  }
402  virtual Gecode::Choice* choice(Space& home) {
403  SteelMill& sm = static_cast<SteelMill&>(home);
404  assert(!sm.slab[start].assigned());
405  // Find order with a) minimum size, b) largest weight
406  unsigned int size = sm.norders;
407  int weight = 0;
408  unsigned int pos = start;
409  for (unsigned int i = start; i<sm.norders; ++i) {
410  if (!sm.slab[i].assigned()) {
411  if (sm.slab[i].size() == size &&
412  sm.orders[i][order_weight] > weight) {
413  weight = sm.orders[i][order_weight];
414  pos = i;
415  } else if (sm.slab[i].size() < size) {
416  size = sm.slab[i].size();
417  weight = sm.orders[i][order_weight];
418  pos = i;
419  }
420  }
421  }
422  unsigned int val = sm.slab[pos].min();
423  // Find first still empty slab (all such slabs are symmetric)
424  unsigned int firstzero = 0;
425  while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
426  ++firstzero;
427  assert(pos < sm.nslabs &&
428  val < sm.norders);
429  return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
430  }
431  virtual Choice* choice(const Space&, Archive& e) {
432  unsigned int alt; int pos, val;
433  e >> alt >> pos >> val;
434  return new Choice(*this, alt, pos, val);
435  }
437  virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
438  unsigned int a) {
439  SteelMill& sm = static_cast<SteelMill&>(home);
440  const Choice& c = static_cast<const Choice&>(_c);
441  if (a)
442  return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
443  ? ES_FAILED : ES_OK;
444  else
445  return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
446  ? ES_FAILED : ES_OK;
447  }
449  virtual Actor* copy(Space& home, bool share) {
450  return new (home) SteelMillBranch(home, share, *this);
451  }
453  static BrancherHandle post(Home home) {
454  return *new (home) SteelMillBranch(home);
455  }
457  virtual size_t dispose(Space&) {
458  return sizeof(*this);
459  }
460  };
461 };
462 
466 int
467 main(int argc, char* argv[]) {
468  SteelMillOptions opt("Steel Mill Slab design");
471  opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
473  opt.solutions(0);
474  if (!opt.parse(argc,argv))
475  return 1;
476  Script::run<SteelMill,BAB,SteelMillOptions>(opt);
477  return 0;
478 }
479 
480 
481 void
483  Options::help();
484  std::cerr << "\t(string), optional" << std::endl
485  << "\t\tBenchmark to load." << std::endl
486  << "\t\tIf none is given, the standard CSPLib instance is used."
487  << std::endl;
488  std::cerr << "\t(unsigned int), optional" << std::endl
489  << "\t\tNumber of orders to use, in the interval [0..norders]."
490  << std::endl
491  << "\t\tIf none is given, all orders are used." << std::endl;
492 }
493 
494 bool
495 SteelMillOptions::parse(int& argc, char* argv[]) {
496  Options::parse(argc,argv);
497  // Check number of arguments
498  if (argc >= 4) {
499  std::cerr << "Too many arguments given, max two allowed (given={";
500  for (int i = 1; i < argc; ++i) {
501  std::cerr << "\"" << argv[i] << "\"";
502  if (i < argc-1) std::cerr << ",";
503  }
504  std::cerr << "})." << std::endl;
505  return false;
506  }
507  // Parse options
508  while (argc >= 2) {
509  bool issize = true;
510  for (int i = strlen(argv[argc-1]); i-- && issize; )
511  issize &= (isdigit(argv[argc-1][i]) != 0);
512  if (issize) {
513  _size = atoi(argv[argc-1]);
514  } else {
515  std::ifstream instance(argv[argc-1]);
516  if (instance.fail()) {
517  std::cerr << "Argument \"" << argv[argc-1]
518  << "\" is neither an integer nor a readable file"
519  << std::endl;
520  return false;
521  }
522  // Read file instance
523  instance >> _ncapacities;
524  _capacities = new int[_ncapacities];
525  _maxcapacity = -1;
526  for (int i = 0; i < _ncapacities; ++i) {
527  instance >> _capacities[i];
528  _maxcapacity = std::max(_maxcapacity, _capacities[i]);
529  }
530  instance >> _ncolors >> _norders;
531  _orders = new int[_norders][2];
532  for (unsigned int i = 0; i < _norders; ++i) {
533  instance >> _orders[i][order_weight] >> _orders[i][order_color];
534  }
535  }
536 
537  --argc;
538  }
539  // Compute loss
540  {
541  _loss = new int[_maxcapacity+1];
542  _loss[0] = 0;
543  int currcap = 0;
544  for (int c = 1; c < _maxcapacity; ++c) {
545  if (c > _capacities[currcap]) ++currcap;
546  _loss[c] = _capacities[currcap] - c;
547  }
548  }
549  // Set size, if none given
550  if (_size == 0) {
551  _size = _norders;
552  }
553  // Check size reasonability
554  if (_size == 0 || _size > _norders) {
555  std::cerr << "Size must be between 1 and " << _norders << std::endl;
556  return false;
557  }
558  return true;
559 }
560 
561 // Positions in order array
562 const int order_weight = 0;
563 const int order_color = 1;
564 
565 // CSPLib instance
567  {12, 14, 17, 18, 19,
568  20, 23, 24, 25, 26,
569  27, 28, 29, 30, 32,
570  35, 39, 42, 43, 44};
571 unsigned int csplib_ncapacities = 20;
572 unsigned int csplib_maxcapacity = 44;
573 int csplib_loss[45];
574 unsigned int csplib_ncolors = 89;
575 unsigned int csplib_norders = 111;
576 int csplib_orders[][2] = {
577  {4, 1},
578  {22, 2},
579  {9, 3},
580  {5, 4},
581  {8, 5},
582  {3, 6},
583  {3, 4},
584  {4, 7},
585  {7, 4},
586  {7, 8},
587  {3, 6},
588  {2, 6},
589  {2, 4},
590  {8, 9},
591  {5, 10},
592  {7, 11},
593  {4, 7},
594  {7, 11},
595  {5, 10},
596  {7, 11},
597  {8, 9},
598  {3, 1},
599  {25, 12},
600  {14, 13},
601  {3, 6},
602  {22, 14},
603  {19, 15},
604  {19, 15},
605  {22, 16},
606  {22, 17},
607  {22, 18},
608  {20, 19},
609  {22, 20},
610  {5, 21},
611  {4, 22},
612  {10, 23},
613  {26, 24},
614  {17, 25},
615  {20, 26},
616  {16, 27},
617  {10, 28},
618  {19, 29},
619  {10, 30},
620  {10, 31},
621  {23, 32},
622  {22, 33},
623  {26, 34},
624  {27, 35},
625  {22, 36},
626  {27, 37},
627  {22, 38},
628  {22, 39},
629  {13, 40},
630  {14, 41},
631  {16, 27},
632  {26, 34},
633  {26, 42},
634  {27, 35},
635  {22, 36},
636  {20, 43},
637  {26, 24},
638  {22, 44},
639  {13, 45},
640  {19, 46},
641  {20, 47},
642  {16, 48},
643  {15, 49},
644  {17, 50},
645  {10, 28},
646  {20, 51},
647  {5, 52},
648  {26, 24},
649  {19, 53},
650  {15, 54},
651  {10, 55},
652  {10, 56},
653  {13, 57},
654  {13, 58},
655  {13, 59},
656  {12, 60},
657  {12, 61},
658  {18, 62},
659  {10, 63},
660  {18, 64},
661  {16, 65},
662  {20, 66},
663  {12, 67},
664  {6, 68},
665  {6, 68},
666  {15, 69},
667  {15, 70},
668  {15, 70},
669  {21, 71},
670  {30, 72},
671  {30, 73},
672  {30, 74},
673  {30, 75},
674  {23, 76},
675  {15, 77},
676  {15, 78},
677  {27, 79},
678  {27, 80},
679  {27, 81},
680  {27, 82},
681  {27, 83},
682  {27, 84},
683  {27, 79},
684  {27, 85},
685  {27, 86},
686  {10, 87},
687  {3, 88}
688 };
689 
690 // STATISTICS: example-any