# 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.

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.