You are here

Data and results for the Steel Mill Slab Problem

Slab image

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] An Efficient Model and Strategy for the Steel Mill Slab Design Problem, Antoine Gargani and Philippe Refalo, CP2007

[2] The Steel Mill Slab Design Problem Revisited, Pascal Van Hentenryck and Laurent Michel, CPAIOR08

[3] 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, (2011)

[4] Solving steel mill slab design problems, Stefan Heinz, Thomas Schlechte, Rüdiger Stephan, Michael Winkler, Constraints 2012

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).

  • pschaus at gmail dot com
  • jean-noel.monette at uclouvain dot be
  • cjc at cs dot brown dot edu

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.

Instance Total Loss Solution due to
bench_2_0 0
bench_2_1 54 Stefan Heinz (SCIP Solver)
bench_2_2 100 Stefan Heinz (SCIP Solver)
bench_2_3 34 Stefan Heinz (SCIP Solver)
bench_2_4 15 Stefan Heinz (SCIP Solver)
bench_2_5 36 Stefan Heinz (SCIP Solver)
bench_2_6 40 Stefan Heinz (SCIP Solver)
bench_2_7 42 Stefan Heinz (SCIP Solver)
bench_2_8 531
bench_2_9 76
bench_2_10 66 Stefan Heinz (SCIP Solver)
bench_2_11 64 Stefan Heinz (SCIP Solver)
bench_2_12 19 Stefan Heinz (SCIP Solver)
bench_2_13 78 Stefan Heinz (SCIP Solver)
bench_2_14 44 Stefan Heinz (SCIP Solver)
bench_2_15 296
bench_2_16 56 Stefan Heinz (SCIP Solver)
bench_2_17 155 Stefan Heinz (SCIP Solver)
bench_2_18 36 Stefan Heinz (SCIP Solver)
bench_2_19 36 Stefan Heinz (SCIP Solver)
Instance Total Loss Solution due to
bench_3_0 5 Stefan Heinz (SCIP Solver)
bench_3_1 15 Stefan Heinz (SCIP Solver)
bench_3_2 10 Stefan Heinz (SCIP Solver)
bench_3_3 14 Stefan Heinz (SCIP Solver)
bench_3_4 7 Stefan Heinz (SCIP Solver)
bench_3_5 35
bench_3_6 11 Stefan Heinz (SCIP Solver)
bench_3_7 39 Stefan Heinz (SCIP Solver)
bench_3_8 63 Stefan Heinz (SCIP Solver)
bench_3_9 155 Stefan Heinz (SCIP Solver)
bench_3_10 39 Stefan Heinz (SCIP Solver)
bench_3_11 14 Stefan Heinz (SCIP Solver)
bench_3_12 6 Stefan Heinz (SCIP Solver)
bench_3_13 19 Stefan Heinz (SCIP Solver)
bench_3_14 15 Stefan Heinz (SCIP Solver)
bench_3_15 45
bench_3_16 35 Stefan Heinz (SCIP Solver)
bench_3_17 8 Stefan Heinz (SCIP Solver)
bench_3_18 22 Stefan Heinz (SCIP Solver)
bench_3_19 17 Stefan Heinz (SCIP Solver)
Instance Total Loss Solution due to
bench_4_0 32 Stefan Heinz (SCIP Solver)
bench_4_1 18
bench_4_2 10 Stefan Heinz (SCIP Solver)
bench_4_3 7 Stefan Heinz (SCIP Solver)
bench_4_4 8
bench_4_5 6
bench_4_6 6 Stefan Heinz (SCIP Solver)
bench_4_7 3
bench_4_8 1
bench_4_9 12 Stefan Heinz (SCIP Solver)
bench_4_10 13 Stefan Heinz (SCIP Solver)
bench_4_11 8 Stefan Heinz (SCIP Solver)
bench_4_12 1 Stefan Heinz (SCIP Solver)
bench_4_13 19 Stefan Heinz (SCIP Solver)
bench_4_14 1
bench_4_15 11 Stefan Heinz (SCIP Solver)
bench_4_16 15 Stefan Heinz (SCIP Solver)
bench_4_17 0
bench_4_18 5
bench_4_19 12 Stefan Heinz (SCIP Solver)
Instance Total Loss Solution due to
bench_5_0 0
bench_5_1 21 Stefan Heinz (SCIP Solver)
bench_5_2 5 Stefan Heinz (SCIP Solver)
bench_5_3 1 Stefan Heinz (SCIP Solver)
bench_5_4 9 Stefan Heinz (SCIP Solver)
bench_5_5 8 Stefan Heinz (SCIP Solver)
bench_5_6 0
bench_5_7 0
bench_5_8 1 Stefan Heinz (SCIP Solver)
bench_5_9 2 Stefan Heinz (SCIP Solver)
bench_5_10 7 Stefan Heinz (SCIP Solver)
bench_5_11 5 Stefan Heinz (SCIP Solver)
bench_5_12 17 Stefan Heinz (SCIP Solver)
bench_5_13 7 Stefan Heinz (SCIP Solver)
bench_5_14 2
bench_5_15 10 Stefan Heinz (SCIP Solver)
bench_5_16 5
bench_5_17 11 Stefan Heinz (SCIP Solver)
bench_5_18 15 Stefan Heinz (SCIP Solver)
bench_5_19 0
Instance Total Loss Solution due to
bench_6_0 0
bench_6_1 19 Stefan Heinz (SCIP Solver)
bench_6_2 0 Stefan Heinz (SCIP Solver)
bench_6_3 0
bench_6_4 0
bench_6_5 1 Stefan Heinz (SCIP Solver)
bench_6_6 0 Stefan Heinz (SCIP Solver)
bench_6_7 0
bench_6_8 0
bench_6_9 1
bench_6_10 0 Stefan Heinz (SCIP Solver)
bench_6_11 7
bench_6_12 0
bench_6_13 12 Stefan Heinz (SCIP Solver)
bench_6_14 2 Stefan Heinz (SCIP Solver)
bench_6_15 3 Stefan Heinz (SCIP Solver)
bench_6_16 0
bench_6_17 0
bench_6_18 0
bench_6_19 0 Stefan Heinz (SCIP Solver)
Instance Total Loss Solution due to
bench_7_0 0
bench_7_1 0
bench_7_2 1 Stefan Heinz (SCIP Solver)
bench_7_3 0
bench_7_4 1 Stefan Heinz (SCIP Solver)
bench_7_5 2 Stefan Heinz (SCIP Solver)
bench_7_6 0
bench_7_7 1 Stefan Heinz (SCIP Solver)
bench_7_8 0
bench_7_9 0
bench_7_10 7
bench_7_11 0
bench_7_12 2
bench_7_13 4
bench_7_14 0
bench_7_15 0
bench_7_16 0
bench_7_17 1
bench_7_18 0
bench_7_19 1
Instance Total Loss Solution due to
bench_8_0 0
bench_8_1 0
bench_8_2 0
bench_8_3 0
bench_8_4 0
bench_8_5 0
bench_8_6 0
bench_8_7 0
bench_8_8 0
bench_8_9 0
bench_8_10 0
bench_8_11 0
bench_8_12 0
bench_8_13 6
bench_8_14 0
bench_8_15 0
bench_8_16 0
bench_8_17 0
bench_8_18 0
bench_8_19 0
Instance Total Loss Solution due to
bench_9_0 0
bench_9_1 0
bench_9_2 0
bench_9_3 0
bench_9_4 0
bench_9_5 0
bench_9_6 0
bench_9_7 0
bench_9_8 0
bench_9_9 0
bench_9_10 0
bench_9_11 0
bench_9_12 3 Stefan Heinz (SCIP Solver)
bench_9_13 0
bench_9_14 0
bench_9_15 0
bench_9_16 0
bench_9_17 0
bench_9_18 0
bench_9_19 0
Instance Total Loss Solution due to
bench_10_0 0
bench_10_1 0
bench_10_2 0
bench_10_3 0
bench_10_4 0
bench_10_5 0
bench_10_6 0
bench_10_7 0
bench_10_8 0
bench_10_9 0
bench_10_10 1
bench_10_11 0
bench_10_12 0
bench_10_13 0
bench_10_14 0
bench_10_15 0
bench_10_16 0
bench_10_17 1
bench_10_18 0
bench_10_19 0
Instance Total Loss Solution due to
bench_11_0 0
bench_11_1 0
bench_11_2 0
bench_11_3 0
bench_11_4 0
bench_11_5 0
bench_11_6 0
bench_11_7 0
bench_11_8 0
bench_11_9 0
bench_11_10 0
bench_11_11 0
bench_11_12 0
bench_11_13 0
bench_11_14 0
bench_11_15 0
bench_11_16 0
bench_11_17 0
bench_11_18 0
bench_11_19 0
Instance Total Loss Solution due to
bench_12_0 0
bench_12_1 0
bench_12_2 0
bench_12_3 0
bench_12_4 0
bench_12_5 0
bench_12_6 0
bench_12_7 0
bench_12_8 5
bench_12_9 0
bench_12_10 0
bench_12_11 0
bench_12_12 0
bench_12_13 0
bench_12_14 0
bench_12_15 0
bench_12_16 0
bench_12_17 0
bench_12_18 0
bench_12_19 0
Instance Total Loss Solution due to
bench_13_0 0
bench_13_1 0
bench_13_2 0
bench_13_3 0
bench_13_4 0
bench_13_5 0
bench_13_6 0
bench_13_7 0
bench_13_8 0
bench_13_9 0
bench_13_10 0
bench_13_11 0
bench_13_12 0
bench_13_13 0
bench_13_14 0
bench_13_15 0
bench_13_16 0
bench_13_17 0
bench_13_18 0
bench_13_19 0
Instance Total Loss Solution due to
bench_14_0 0
bench_14_1 0
bench_14_2 0
bench_14_3 0
bench_14_4 0
bench_14_5 0
bench_14_6 0
bench_14_7 0
bench_14_8 0
bench_14_9 0
bench_14_10 0
bench_14_11 0
bench_14_12 0
bench_14_13 0
bench_14_14 0
bench_14_15 0
bench_14_16 0
bench_14_17 0
bench_14_18 0
bench_14_19 0
Instance Total Loss Solution due to
bench_15_0 0
bench_15_1 0
bench_15_2 0
bench_15_3 0
bench_15_4 0
bench_15_5 0
bench_15_6 0
bench_15_7 0
bench_15_8 0
bench_15_9 0
bench_15_10 0
bench_15_11 0
bench_15_12 0
bench_15_13 0
bench_15_14 0
bench_15_15 0
bench_15_16 0
bench_15_17 0
bench_15_18 0
bench_15_19 0
Instance Total Loss Solution due to
bench_16_0 0
bench_16_1 0
bench_16_2 0
bench_16_3 0
bench_16_4 0
bench_16_5 0
bench_16_6 0
bench_16_7 0
bench_16_8 0
bench_16_9 0
bench_16_10 0
bench_16_11 0
bench_16_12 0
bench_16_13 0
bench_16_14 0
bench_16_15 0
bench_16_16 0
bench_16_17 0
bench_16_18 0
bench_16_19 0
Instance Total Loss Solution due to
bench_17_0 0
bench_17_1 0
bench_17_2 0
bench_17_3 0
bench_17_4 0
bench_17_5 0
bench_17_6 0
bench_17_7 0
bench_17_8 0
bench_17_9 0
bench_17_10 0
bench_17_11 0
bench_17_12 0
bench_17_13 0
bench_17_14 0
bench_17_15 0
bench_17_16 0
bench_17_17 0
bench_17_18 0
bench_17_19 0
Instance Total Loss Solution due to
bench_18_0 0
bench_18_1 0
bench_18_2 0
bench_18_3 0
bench_18_4 0
bench_18_5 0
bench_18_6 0
bench_18_7 0
bench_18_8 0
bench_18_9 0
bench_18_10 0
bench_18_11 0
bench_18_12 0
bench_18_13 0
bench_18_14 0
bench_18_15 0
bench_18_16 0
bench_18_17 0
bench_18_18 0
bench_18_19 0
Instance Total Loss Solution due to
bench_19_0 0
bench_19_1 0
bench_19_2 0
bench_19_3 0
bench_19_4 0
bench_19_5 0
bench_19_6 0
bench_19_7 0
bench_19_8 0
bench_19_9 0
bench_19_10 0
bench_19_11 0
bench_19_12 0
bench_19_13 0
bench_19_14 0
bench_19_15 0
bench_19_16 0
bench_19_17 0
bench_19_18 0
bench_19_19 0
Instance Total Loss Solution due to
bench_20_0 0
bench_20_1 0
bench_20_2 0
bench_20_3 0
bench_20_4 0
bench_20_5 0
bench_20_6 0
bench_20_7 0
bench_20_8 0
bench_20_9 0
bench_20_10 0
bench_20_11 0
bench_20_12 0
bench_20_13 0
bench_20_14 0
bench_20_15 0
bench_20_16 0
bench_20_17 0
bench_20_18 0
bench_20_19 0
AttachmentSize
steelmillslab_benchs.tgz13.26 KB
steelmillslab_111orders.txt812 bytes