You are here

Solving Steel Mill Slab Problems with Constraint-Based Techniques: CP, LNS, and CBLS

TitleSolving Steel Mill Slab Problems with Constraint-Based Techniques: CP, LNS, and CBLS
Publication TypeJournal Article
Year of Publication2011
AuthorsSchaus, Pierre, Van Hentenryck Pascal, Monette Jean-Noël, Coffrin C., Michel L., and Deville Yves
JournalJournal of Constraints

The Steel Mill Slab Problem is an optimization benchmark that has been studied for a long time in the constraint-programming community but was only solved efficiently in the two last years. Gargani and Refalo solved the problem using Large Neighborhood Search and Van Hentenryck and Michel made use of constraint programming with an improved symmetry breaking scheme. In the first part of this paper, we build on those approaches, present improvements of those two techniques, and study how the problem can be tackled by Constraint-Based Local Search. As a result, the classical instances of CSPLib can now be solved in less than 50ms. To improve our understanding of this problem, we also introduce a new set of harder instances, which highlight the strengths and the weaknesses of the various approaches. In a second part of the paper, we present a variation of the Steel Mill Slab Problem whose aim is to minimize the number of slabs. We show how this problem can be tackled with slight modifications of our proposed algorithms. In particular, the constraint-programming solution is enhanced by a global symmetric cardinality constraint, which, to our knowledge, has never been implemented and used before. All the proposed approaches to solve this problem have been modeled and evaluated using Comet.