Data and results for the Steel Mill Slab Problem

The Steel Mill Slab problem is the problem 38 of CSPLib:

The steel mill slab problem is to assign colored sized orders to slabs of different capacities such that the total loss is minimized and such that at most two differentz colors are present in each slabs. We call this problem the Steel Mill Slab Problem of Type 1 (SMSP1).

Since the instance from CSPLib with 111 orders is now too easy to solve with the recent models for this problem, we generated a set of 19 × 20; instances of increasing difficulty by generating new slab capacities (order sizes and colors are the same as in the CSPLib real instance). The difficulty increases as the number of slab capacities decreases.

Download the instances. The CSPLib instance.

Format:

"number of slab capacities" "sequence of capacities in increasing order"
"number of colors"
"number of orders"
"size order 1" "color of order 1"
"size order 2" "color of order 2"
...

A variant of the problem more related to bin-packing that was suggested in [1] is the following:

Given an upper-bound on the total loss, assign colored sized orders to slabs of different capacities such that the total loss does not exceed the given total loss and such that the number of slabs is minimized. We call this problem the Steel Mill Slab Problem of Type 2 (SMSP2).

Only SMSP1 is considered here, some results can be found in [1] for SMSP2 with the CSPLib instance.

Recent References

[1] Solving Steel Mill Slab Problems with Constraint-Based Techniques: CP, LNS, and CBLS, Schaus, Pierre, Van Hentenryck Pascal, Monette Jean-Noël, Coffrin C., Michel L., and Deville Yves , Journal of Constraints, (2010)
[2] The Steel Mill Slab Design Problem Revisited, Pascal Van Hentenryck and Laurent Michel, CPAIOR08
[3] An Efficient Model and Strategy for the Steel Mill Slab Design Problem, Antoine Gargani and Philippe Refalo, CP2007

Programs and ressource

The two different Constraint Based Local Search (CBLS) implementations described in [1] were written in Comet. They allowed to generate most of the results given below.

After our work, Stefan Heinz has improved many of the difficult instances using a column generation approach with SCIP Solver.

Results on the instances

About 100/380 instances have an optimal loss larger than 0 and were not proven to be optimal. These instances can be considered as open problems.

Therefore, interested researchers are asked for sending data of optimal or improving solutions to these instances as soon as they are found by any solution procedure.

Please send an email (to one of the persons below) containing the name of the instance, the given loss and a list of the slab numbers to which each order is assigned to (in their order).

Example of mail: bench_19_7 0 3 0 2 3 4 … To give a solution to the instance bench_19_7 with a total loss 0, first order is assigned to slab 3, second order to slab 0 …(slabs are numbered from 0).

If the solution imroves the best known solution the new optimal value will be added to the list together with the name of the person who found it. Send also any references/papers describing your paper such that we can add it in the reference section.