Strengthening the formulation of mixed integer programs with an example in production scheduling

Thursday, July 28, 2005 - 9:30am - 10:15am
EE/CS 3-180
Kent Andersen (Université Catholique de Louvain)
Joint work with Yves Pochet.

We consider the following question: Is it possible to replace a constraint
of a MIP formulation with a new and tighter inequality? We
show that, if there is a valid inequality, which dominates a constraint
of the formulation, then there is a coefficient in the formulation that
can be strengthened. We also show that an algorithm, which is based
on strengthening one coefficient at a time, stops after a finite number
of strengthening steps. We give examples for which the difference between
the quality of the original formulation and a resulting strengthened
formulation is relatively large: on some problems, the effect of
modifying the coefficients in the original formulation is larger than the
effect of adding a large number of cutting planes (in terms of amount
of integrality gap closed). For instance, on one MIPLIB instance, all
of the integrality gap is closed by strengthening the coefficients in the
initial formulation while optimizing over the first Chvatal closure only
closes 61% of the integrality gap. We also solve another hard instance
to optimality by strengthening coefficients in every round of a
cutting plane algorithm based on mixed integer Gomory cuts and split
cuts. The same cutting plane algorithm was unable to solve this instance
without including the strengthening step. The instance was only
recently solved with an approach based on the first Chvatal closure.

We finish by demonstrating how coefficient strengthening can be
used to design a model for a production scheduling problem. First, an
initial formulation of a small problem is produced, and the coefficients
in this formulation are strengthened with expensive techniques. The
resulting formulation is then evaluated by tracing the logic of each
strengthened coefficient. The result is a new understanding of how to
build a tight formulation of the problem. We believe this suggests that
it might be of interest to construct a tool for strengthening coefficients.