## Solving Steel Mill Slab Problems with Branch and Price

Please always quote using this URN: urn:nbn:de:0297-zib-11260

- The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.

Author: | Stefan Heinz, Rüdiger Stephan, Thomas Schlechte |
---|---|

Document Type: | ZIB-Report |

Tag: | branch-and-price; integer programming; steel mill slab problem |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming | |

Date of first Publication: | 2009/04/29 |

Series (Serial Number): | ZIB-Report (09-14) |

ISSN: | 1438-0064 |

ZIB-Reportnumber: | 09-14 |