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.

[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, , Journal of Constraints, (2011)

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

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.

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 |

Attachment | Size |
---|---|

steelmillslab_benchs.tgz | 13.26 KB |

steelmillslab_111orders.txt | 812 bytes |