Generated on Mon Sep 17 2012 22:20:32 for Gecode by doxygen 1.8.1.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: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11  * $Revision: 12001 $
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 
118 
147 class SteelMill : public MinimizeScript {
148 protected:
152  int* capacities;
155  int* loss;
156  int ncolors;
158  unsigned int norders;
159  unsigned int nslabs;
160 
161 
165  IntVarArray slab,
166  slabload,
167  slabcost;
169 
170 
171 public:
173  enum {
175  SYMMETRY_BRANCHING
176  };
177 
180  : // Initialize instance data
181  capacities(opt.capacities()), ncapacities(opt.ncapacities()),
182  maxcapacity(opt.maxcapacity()), loss(opt.loss()),
183  ncolors(opt.ncolors()), orders(opt.orders()),
184  norders(opt.size()), nslabs(opt.size()),
185  // Initialize problem variables
186  slab(*this, norders, 0,nslabs-1),
187  slabload(*this, nslabs, 0,45),
188  slabcost(*this, nslabs, 0, Int::Limits::max),
189  total_cost(*this, 0, Int::Limits::max)
190  {
191  // Boolean variables for slab[o]==s
192  BoolVarArgs boolslab(norders*nslabs);
193  for (unsigned int i = 0; i < norders; ++i) {
194  BoolVarArgs tmp(nslabs);
195  for (int j = nslabs; j--; ) {
196  boolslab[j + i*nslabs] = tmp[j] = BoolVar(*this, 0, 1);
197  }
198  channel(*this, tmp, slab[i]);
199  }
200 
201  // Packing constraints
202  for (unsigned int s = 0; s < nslabs; ++s) {
203  IntArgs c(norders);
204  BoolVarArgs x(norders);
205  for (int i = norders; i--; ) {
206  c[i] = orders[i][order_weight];
207  x[i] = boolslab[s + i*nslabs];
208  }
209  linear(*this, c, x, IRT_EQ, slabload[s]);
210  }
211  // Redundant packing constraint
212  int totalweight = 0;
213  for (unsigned int i = norders; i-- ; )
214  totalweight += orders[i][order_weight] ;
215  linear(*this, slabload, IRT_EQ, totalweight);
216 
217 
218  // Color constraints
219  IntArgs nofcolor(ncolors);
220  for (int c = ncolors; c--; ) {
221  nofcolor[c] = 0;
222  for (int o = norders; o--; ) {
223  if (orders[o][order_color] == c) nofcolor[c] += 1;
224  }
225  }
226  BoolVar f(*this, 0, 0);
227  for (unsigned int s = 0; s < nslabs; ++s) {
228  BoolVarArgs hascolor(ncolors);
229  for (int c = ncolors; c--; ) {
230  if (nofcolor[c]) {
231  BoolVarArgs hasc(nofcolor[c]);
232  int pos = 0;
233  for (int o = norders; o--; ) {
234  if (orders[o][order_color] == c)
235  hasc[pos++] = boolslab[s + o*nslabs];
236  }
237  assert(pos == nofcolor[c]);
238  hascolor[c] = BoolVar(*this, 0, 1);
239  rel(*this, BOT_OR, hasc, hascolor[c]);
240  } else {
241  hascolor[c] = f;
242  }
243  }
244  linear(*this, hascolor, IRT_LQ, 2);
245  }
246 
247  // Compute slabcost
248  IntArgs l(maxcapacity, loss);
249  for (int s = nslabs; s--; ) {
250  element(*this, l, slabload[s], slabcost[s]);
251  }
252  linear(*this, slabcost, IRT_EQ, total_cost);
253 
254  // Add branching
255  if (opt.symmetry() == SYMMETRY_BRANCHING) {
256  // Symmetry breaking branching
257  SteelMillBranch::post(*this);
258  } else { // opt.symmetry() == SYMMETRY_NONE
259  branch(*this, slab, INT_VAR_MAX_MIN, INT_VAL_MIN);
260  }
261  }
262 
264  virtual void
265  print(std::ostream& os) const {
266  os << "What slab=" << slab << std::endl;
267  os << "Slab load=" << slabload << std::endl;
268  os << "Slab cost=" << slabcost << std::endl;
269  os << "Total cost=" << total_cost << std::endl;
270  int nslabsused = 0;
271  int nslabscost = 0;
272  bool unassigned = false;
273  for (int i = nslabs; i--; ) {
274  if (!slabload[i].assigned() || !slabcost[i].assigned()) {
275  unassigned = true;
276  break;
277  }
278  if (slabload[i].min()>0) ++nslabsused;
279  if (slabcost[i].min()>0) ++nslabscost;
280  }
281  if (!unassigned)
282  os << "Number of slabs used=" << nslabsused
283  << ", slabs with cost=" << nslabscost
284  << std::endl;
285  os << std::endl;
286  }
287 
289  SteelMill(bool share, SteelMill& s)
290  : MinimizeScript(share,s),
291  capacities(s.capacities), ncapacities(s.ncapacities),
292  maxcapacity(s.maxcapacity), loss(s.loss),
293  ncolors(s.ncolors), orders(s.orders),
294  norders(s.norders), nslabs(s.nslabs) {
295  slab.update(*this, share, s.slab);
296  slabload.update(*this, share, s.slabload);
297  slabcost.update(*this, share, s.slabcost);
298  total_cost.update(*this, share, s.total_cost);
299  }
301  virtual Space*
302  copy(bool share) {
303  return new SteelMill(share,*this);
304  }
306  virtual IntVar cost(void) const {
307  return total_cost;
308  }
309 
310 
320  protected:
322  mutable int start;
324  class Choice : public Gecode::Choice {
325  public:
327  int pos;
329  int val;
333  Choice(const Brancher& b, unsigned int a, int pos0, int val0)
334  : Gecode::Choice(b,a), pos(pos0), val(val0) {}
336  virtual size_t size(void) const {
337  return sizeof(Choice);
338  }
340  virtual void archive(Archive& e) const {
342  e << alternatives() << pos << val;
343  }
344  };
345 
348  : Brancher(home), start(0) {}
350  SteelMillBranch(Space& home, bool share, SteelMillBranch& b)
351  : Brancher(home, share, b), start(b.start) {
352  }
353 
354  public:
356  virtual bool status(const Space& home) const {
357  const SteelMill& sm = static_cast<const SteelMill&>(home);
358  for (unsigned int i = start; i < sm.norders; ++i)
359  if (!sm.slab[i].assigned()) {
360  start = i;
361  return true;
362  }
363  // No non-assigned orders left
364  return false;
365  }
367  virtual Gecode::Choice* choice(Space& home) {
368  SteelMill& sm = static_cast<SteelMill&>(home);
369  assert(!sm.slab[start].assigned());
370  // Find order with a) minimum size, b) largest weight
371  unsigned int size = sm.norders;
372  int weight = 0;
373  unsigned int pos = start;
374  for (unsigned int i = start; i<sm.norders; ++i) {
375  if (!sm.slab[i].assigned()) {
376  if (sm.slab[i].size() == size &&
377  sm.orders[i][order_weight] > weight) {
378  weight = sm.orders[i][order_weight];
379  pos = i;
380  } else if (sm.slab[i].size() < size) {
381  size = sm.slab[i].size();
382  weight = sm.orders[i][order_weight];
383  pos = i;
384  }
385  }
386  }
387  unsigned int val = sm.slab[pos].min();
388  // Find first still empty slab (all such slabs are symmetric)
389  unsigned int firstzero = 0;
390  while (firstzero < sm.nslabs && sm.slabload[firstzero].min() > 0)
391  ++firstzero;
392  assert(pos < sm.nslabs &&
393  val < sm.norders);
394  return new Choice(*this, (val<firstzero) ? 2 : 1, pos, val);
395  }
396  virtual Choice* choice(const Space&, Archive& e) {
397  unsigned int alt; int pos, val;
398  e >> alt >> pos >> val;
399  return new Choice(*this, alt, pos, val);
400  }
402  virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
403  unsigned int a) {
404  SteelMill& sm = static_cast<SteelMill&>(home);
405  const Choice& c = static_cast<const Choice&>(_c);
406  if (a)
407  return me_failed(Int::IntView(sm.slab[c.pos]).nq(home, c.val))
408  ? ES_FAILED : ES_OK;
409  else
410  return me_failed(Int::IntView(sm.slab[c.pos]).eq(home, c.val))
411  ? ES_FAILED : ES_OK;
412  }
414  virtual Actor* copy(Space& home, bool share) {
415  return new (home) SteelMillBranch(home, share, *this);
416  }
418  static void post(Home home) {
419  (void) new (home) SteelMillBranch(home);
420  }
422  virtual size_t dispose(Space&) {
423  return sizeof(*this);
424  }
425  };
426 };
427 
431 int
432 main(int argc, char* argv[]) {
433  SteelMillOptions opt("Steel Mill Slab design");
436  opt.symmetry(SteelMill::SYMMETRY_BRANCHING,"branching");
437  opt.solutions(0);
438  if (!opt.parse(argc,argv))
439  return 1;
440  Script::run<SteelMill,BAB,SteelMillOptions>(opt);
441  return 0;
442 }
443 
444 
445 void
447  Options::help();
448  std::cerr << "\t(string), optional" << std::endl
449  << "\t\tBenchmark to load." << std::endl
450  << "\t\tIf none is given, the standard CSPLib instance is used."
451  << std::endl;
452  std::cerr << "\t(unsigned int), optional" << std::endl
453  << "\t\tNumber of orders to use, in the interval [0..norders]."
454  << std::endl
455  << "\t\tIf none is given, all orders are used." << std::endl;
456 }
457 
458 bool
459 SteelMillOptions::parse(int& argc, char* argv[]) {
460  Options::parse(argc,argv);
461  // Check number of arguments
462  if (argc >= 4) {
463  std::cerr << "Too many arguments given, max two allowed (given={";
464  for (int i = 1; i < argc; ++i) {
465  std::cerr << "\"" << argv[i] << "\"";
466  if (i < argc-1) std::cerr << ",";
467  }
468  std::cerr << "})." << std::endl;
469  return false;
470  }
471  // Parse options
472  while (argc >= 2) {
473  bool issize = true;
474  for (int i = strlen(argv[argc-1]); i-- && issize; )
475  issize &= (isdigit(argv[argc-1][i]) != 0);
476  if (issize) {
477  _size = atoi(argv[argc-1]);
478  } else {
479  std::ifstream instance(argv[argc-1]);
480  if (instance.fail()) {
481  std::cerr << "Argument \"" << argv[argc-1]
482  << "\" is neither an integer nor a readable file"
483  << std::endl;
484  return false;
485  }
486  // Read file instance
487  instance >> _ncapacities;
488  _capacities = new int[_ncapacities];
489  _maxcapacity = -1;
490  for (int i = 0; i < _ncapacities; ++i) {
491  instance >> _capacities[i];
492  _maxcapacity = std::max(_maxcapacity, _capacities[i]);
493  }
494  instance >> _ncolors >> _norders;
495  _orders = new int[_norders][2];
496  for (unsigned int i = 0; i < _norders; ++i) {
497  instance >> _orders[i][order_weight] >> _orders[i][order_color];
498  }
499  }
500 
501  --argc;
502  }
503  // Compute loss
504  {
505  _loss = new int[_maxcapacity+1];
506  _loss[0] = 0;
507  int currcap = 0;
508  for (int c = 1; c < _maxcapacity; ++c) {
509  if (c > _capacities[currcap]) ++currcap;
510  _loss[c] = _capacities[currcap] - c;
511  }
512  }
513  // Set size, if none given
514  if (_size == 0) {
515  _size = _norders;
516  }
517  // Check size reasonability
518  if (_size == 0 || _size > _norders) {
519  std::cerr << "Size must be between 1 and " << _norders << std::endl;
520  return false;
521  }
522  return true;
523 }
524 
525 // Positions in order array
526 const int order_weight = 0;
527 const int order_color = 1;
528 
529 // CSPLib instance
531  {12, 14, 17, 18, 19,
532  20, 23, 24, 25, 26,
533  27, 28, 29, 30, 32,
534  35, 39, 42, 43, 44};
535 unsigned int csplib_ncapacities = 20;
536 unsigned int csplib_maxcapacity = 44;
537 int csplib_loss[45];
538 unsigned int csplib_ncolors = 89;
539 unsigned int csplib_norders = 111;
540 int csplib_orders[][2] = {
541  {4, 1},
542  {22, 2},
543  {9, 3},
544  {5, 4},
545  {8, 5},
546  {3, 6},
547  {3, 4},
548  {4, 7},
549  {7, 4},
550  {7, 8},
551  {3, 6},
552  {2, 6},
553  {2, 4},
554  {8, 9},
555  {5, 10},
556  {7, 11},
557  {4, 7},
558  {7, 11},
559  {5, 10},
560  {7, 11},
561  {8, 9},
562  {3, 1},
563  {25, 12},
564  {14, 13},
565  {3, 6},
566  {22, 14},
567  {19, 15},
568  {19, 15},
569  {22, 16},
570  {22, 17},
571  {22, 18},
572  {20, 19},
573  {22, 20},
574  {5, 21},
575  {4, 22},
576  {10, 23},
577  {26, 24},
578  {17, 25},
579  {20, 26},
580  {16, 27},
581  {10, 28},
582  {19, 29},
583  {10, 30},
584  {10, 31},
585  {23, 32},
586  {22, 33},
587  {26, 34},
588  {27, 35},
589  {22, 36},
590  {27, 37},
591  {22, 38},
592  {22, 39},
593  {13, 40},
594  {14, 41},
595  {16, 27},
596  {26, 34},
597  {26, 42},
598  {27, 35},
599  {22, 36},
600  {20, 43},
601  {26, 24},
602  {22, 44},
603  {13, 45},
604  {19, 46},
605  {20, 47},
606  {16, 48},
607  {15, 49},
608  {17, 50},
609  {10, 28},
610  {20, 51},
611  {5, 52},
612  {26, 24},
613  {19, 53},
614  {15, 54},
615  {10, 55},
616  {10, 56},
617  {13, 57},
618  {13, 58},
619  {13, 59},
620  {12, 60},
621  {12, 61},
622  {18, 62},
623  {10, 63},
624  {18, 64},
625  {16, 65},
626  {20, 66},
627  {12, 67},
628  {6, 68},
629  {6, 68},
630  {15, 69},
631  {15, 70},
632  {15, 70},
633  {21, 71},
634  {30, 72},
635  {30, 73},
636  {30, 74},
637  {30, 75},
638  {23, 76},
639  {15, 77},
640  {15, 78},
641  {27, 79},
642  {27, 80},
643  {27, 81},
644  {27, 82},
645  {27, 83},
646  {27, 84},
647  {27, 79},
648  {27, 85},
649  {27, 86},
650  {10, 87},
651  {3, 88}
652 };
653 
654 // STATISTICS: example-any