038: Steel Mill Slab Design

Download
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 <A HREF="/Problems/prob038/references">references</A> page.

<H4>Slab Variables</H4>
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 <EM>d</EM> orders, a maximum of <EM>d</EM> slabs are required. We use variables <EM>s_1, ..., s_d</EM>, with domains of size <EM>&sigma;</EM> (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 <EM>s_i</EM> is assigned 0 by a particular solution, <EM>s_i</EM> is not used in that solution. The
optimisation function, which must be minimised, is therefore simply the sum of the <EM>s_i</EM> variables.

<H4>The Order Matrix</H4>
A <EM>d x d</EM> 0/1 matrix, <B>orders[]</B>, is used to represent the assignment of orders to slabs, where the <EM>o_i</EM> are the orders:
<PRE>
    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
</PRE>
Constraints on the rows ensure that the slab capacity is not exceeded, where <TT>weight</TT>(<EM>o_i</EM>) gives the weight associated with order <EM>o_i</EM>:
<UL>
<LI><TT>forall</TT> <EM>j</EM> in 1..<EM>d</EM>: <TT>sum</TT>_{<EM>i</EM> in 1..<EM>d</EM>} (<TT>weight</TT>(<EM>o_i</EM>) <EM>x</EM> <B>orders[</B><EM>i</EM>, <EM>j</EM><B>]</B>) <= <EM>s_j</EM>
</UL>
Constraints on the columns ensure that each order is assigned to one and only one slab:
<UL>
<LI><TT>forall</TT> <EM>i</EM> in 1..<EM>d</EM>: <TT>sum</TT>_{<EM>j</EM> in 1..<EM>d</EM>} (<B>orders[</B><EM>i</EM>, <EM>j</EM><B>]</B>) = 1
</UL>

<H4>The Colour Matrix</H4>
A second 0/1 matrix, <B>colours[]</B>, with dimensions <EM>k x d</EM> (recall that <EM>k</EM> is the number of colours) is used to enforce the colour constraints:
<PRE>
    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
</PRE>

Channelling constraints link <B>orders[]</B> to <B>colours[]</B>, where <TT>colour</TT>(<EM>o_i</EM>) gives the colour associated with order <EM>o_i</EM>:
<UL>
<LI> <TT>forall</TT> <EM>i, j</EM> in 1..<EM>d</EM>: <B>orders[</B><EM>i, j</EM><B>]</B> = 1 -> <B>colours[</B><TT>colour</TT>(<EM>o_i</EM>), <EM>j</EM><B>]</B>=1
</UL>

Constraints on the rows of <B>colours[]</B> ensure that orders with at most <EM>p</EM> colours are assigned to each slab:
<UL>
<LI> <TT>forall</TT> <EM>j</EM> in 1..<EM>d</EM>: <TT>sum</TT>_{<EM>i</EM> in 1..<EM>k</EM>} (<B>colours[</B><EM>i</EM>, <EM>j</EM><B>]</B>) <= <EM>p</EM>
</UL>

The slab variables, <EM>s_1, ..., s_d</EM> 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:
<UL>
<LI><EM>s_1 >= s_2 >= ... >= s_d</EM>
</UL>
Furthermore, columns of <B>orders[]</B> 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 <B>orders[</B><EM>i</EM>, _<B>]</B> is the <EM>i</EM>th column of <B>orders[]</B>:
<UL>
<LI><TT>weight</TT>(<EM>o_i</EM>) = <TT>weight</TT>(<EM>o_j</EM>) <TT>AND</TT> <TT>colour</TT>(<EM>o_i</EM>) = <TT>colour</TT>(<EM>o_j</EM>) -> <B>orders[</B><EM>i</EM>, _<B>]</B> >=(lex) <B>orders[</B><EM>j</EM>, _<B>]</B>
</UL>
Lastly, rows of <B>orders[]</B> 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 <B>orders[</B>_, <EM>i</EM><B>]</B> is the <EM>i</EM>th row of <B>orders[]</B>:
<UL>
<LI><TT>forall</TT> <EM>i</EM> in 1..<EM>d-1</EM>: <EM>s_i</EM> = <EM>s</EM>_{<EM>i</EM>+1} -> <B>orders[</B>_, <EM>i</EM><B>]</B> >=(lex) <B>orders[</B>_, <EM>i+1</EM><B>]</B>
</UL>

<H4>Implied Constraints</H4>
Several useful implied constraints can be added to this model, as described in [2].
<OL>
 <LI>
      A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh.
      "<A HREF="http://www.cs.york.ac.uk/aig/projects/implied/docs/CPGACLex.pdf">Global Constraints for Lexicographic Orderings</A>,"
      Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming, pages 93-108, 2002. 
 </LI>
 <LI>
      A. M. Frisch, I. Miguel, T. Walsh.
      "<A HREF="http://www.cs.york.ac.uk/aig/projects/implied/docs/SMillModelling.pdf">Symmetry and Implied Constraints in the Steel Mill Slab Design Problem</A>,"
      Proceedings of the CP'01 Workshop on Modelling and Problem Formulation (Formul'01), pages 8-15, 2001.
 </LI>
 <LI>
     B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh.
     "<A HREF="http://download.springer.com/static/pdf/339/art%253A10.1023%252FB%253AANOR.0000032568.51115.0d.pdf?auth66=1393669700_9ff4010d5fe4a0ec5f0868f17dd23f94&ext=.pdf">Hybrid Modelling for Robust Solving</A>,"   
     Annals of Operations Research 130 (1-4), 19-39, 2003.
 </LI>
</OL>