038: Steel Mill Slab Design

One straightforward way to model this problem is via a matrix model, as described here. See also [3] for a hybrid CP/IP model. More sophisticated models can be found in more recent papers - see the references page.

Slab Variables
If we assume that the greatest order weight does not exceed the maximum slab size, the worst case will involve assigning each order to an individual slab. Hence, given d orders, a maximum of d slabs are required. We use variables s_1, ..., s_d, with domains of size σ (the number of slab sizes the mill can produce) to decide the size of each slab. Generally, some slabs will remain unused, so 0 is added to the domain of each variable such that if s_i is assigned 0 by a particular solution, s_i is not used in that solution. The
optimisation function, which must be minimised, is therefore simply the sum of the s_i variables.

The Order Matrix
A d x d 0/1 matrix, orders[], is used to represent the assignment of orders to slabs, where the o_i are the orders:
    o_1 o_2 ... o_d
s_1 0/1 0/1 ... 0/1
s_2 0/1 0/1 ... 0/1
... ... ... ... ...
s_d 0/1 0/1 ... 0/1

Constraints on the rows ensure that the slab capacity is not exceeded, where weight(o_i) gives the weight associated with order o_i:

forall j in 1..d: sum_{i in 1..d} (weight(o_i) x orders[i, j]) <= s_j

Constraints on the columns ensure that each order is assigned to one and only one slab:

forall i in 1..d: sum_{j in 1..d} (orders[i, j]) = 1


The Colour Matrix
A second 0/1 matrix, colours[], with dimensions k x d (recall that k is the number of colours) is used to enforce the colour constraints:
    red green ... brown
s_1 0/1 0/1   ... 0/1
s_2 0/1 0/1   ... 0/1
... ... ...   ... ...
s_d 0/1 0/1   ... 0/1


Channelling constraints link orders[] to colours[], where colour(o_i) gives the colour associated with order o_i:

 forall i, j in 1..d: orders[i, j] = 1 -> colours[colour(o_i), j]=1


Constraints on the rows of colours[] ensure that orders with at most p colours are assigned to each slab:

 forall j in 1..d: sum_{i in 1..k} (colours[i, j]) <= p


The slab variables, s_1, ..., s_d are indistinguishable: the slab sizes assigned to each of these variables may be permuted without affecting the solution (assuming order assignments are updated appropriately). This symmetry can be broken by ordering the variables. The ordering is as follows so that the `used' slabs appear first:

s_1 >= s_2 >= ... >= s_d

Furthermore, columns of orders[] associated with orders of equal weight and colour are symmetrical. One way of removing this symmetry is to impose a lexicographic order (see [1]) on the symmetrical columns, where orders[i, _] is the ith column of orders[]:

weight(o_i) = weight(o_j) AND colour(o_i) = colour(o_j) -> orders[i, _] >=(lex) orders[j, _]

Lastly, rows of orders[] associated with slabs of an equal size are also symmetrical. Again, this symmetry can be removed by imposing a lexicographic order on the symmetrical rows, where orders[_, i] is the ith row of orders[]:

forall i in 1..d-1: s_i = s_{i+1} -> orders[_, i] >=(lex) orders[_, i+1]


Implied Constraints
Several useful implied constraints can be added to this model, as described in [2].

 

      A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh.
      "Global Constraints for Lexicographic Orderings,"
      Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming, pages 93-108, 2002. 
 
 

      A. M. Frisch, I. Miguel, T. Walsh.
      "Symmetry and Implied Constraints in the Steel Mill Slab Design Problem,"
      Proceedings of the CP'01 Workshop on Modelling and Problem Formulation (Formul'01), pages 8-15, 2001.
 
 

     B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh.
     "Hybrid Modelling for Robust Solving,"   
     Annals of Operations Research 130 (1-4), 19-39, 2003.