Modelling a Steel Mill Slab Design Problem

                              Ian Miguel
                    Department of Computer Science
                          University of York
                            United Kingdom
                          ianm@cs.york.ac.uk
                   http://www.cs.york.ac.uk/~ianm/

This talk considers an industrial steel mill slab design problem. This
problem is an instance of a class of difficult problems where the
problem structure (in this case, the number and size of slabs) is not
fixed initially, but determined as part of the solution process. Since
a natural encoding into a constraint satisfaction problem does not
immediately suggest itself, the choice of model for this type of
problem may be crucial in successfully solving it.

Three different models to tackle the slab design problem are therefore
considered. Model A uses a conservatively large number of variables to
represent the slabs, some of which will typically be redundant in an
optimal solution. Model B operates in two phases, first solving an
abstraction of the original problem before solving further
sub-problems to provide a solution to the original problem. The third
model is a dual model combining models A and B, allowing search and
propagation on both sets of variables.