Solving steel mill slab design problems
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
| Author: | Stefan Heinz, Thomas Schlechte, Rüdiger Stephan, Michael Winkler |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | binpacking with side constraints; integer programming; multiple knapsack problem with color constraints; set partitioning; steel mill slab design problem |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| 90C90 Applications of mathematical programming | |
| 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] | |
| Department: | Optimierung |
| Date of Publication (online): | 29.09.2011 |
| Series / Serial Number | ZIB-Report 11-38 |
| ISSN: | 1438-0064 |
| Published in: | App. in: Constraints 17 (2012) 39-50 DOI 10.1007/s10601-011-9113-8 |




