prob038: Steel Mill Slab Design
Modelling
One straightforward way to model this problem is via a matrix model, as
described here. See also [3] for a hybrid CP/IP model.
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
Symmetry
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:
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 (to appear), 2003.
Back to CSPLib home page.