Campuses:

Constraint branching and disjunctive cuts for mixed integer programs

Thursday, July 28, 2005 - 10:15am - 11:00am
EE/CS 3-180
Michael Perregaard (Dash Associates)
Several disjunctive cuts for mixed integer programs are (directly or
indirectly) based on imposing a simple disjunction where a single
fractional variable is required to be rounded either up or down to its
nearest integer value. Two well-known cut families based on such a
disjunction is Gomory's mixed integer cut and the lift-and-project cuts
from the 1990s. Both cut classes involves strengthening by considering
the integrality of other variables. This strengthening can be
interpreted as a modification of the underlying simple disjunction.
Later research into disjunctive cuts have taken this idea of
strengthening the underlying disjunction even further.

The most common method for solving a mixed integer program is by
branch-and-bound. Almost all such available codes branch on a single
variable at a time. For general mixed integer programs, where the
integer variables are allowed a wider range than simple 0-1 variables,
such a simple branching scheme can often lead to an explosion in the
number of nodes the code has to search. In this talk I examine the
feasibility of applying the ideas for strengthening cuts to the simple
branching disjunctions for the purpose of creating better mixed integer
branches. Results from computational tests on a variety of public
benchmark problems, using an implementation based on the Xpress-MP
solver, will be used to demonstrate the effects of such strengthened
branches.