Seminars & Events

Argonne National Laboratory Mathematics and Computer Science Division Seminar
"In search of optimal disjunctions in Mixed Integer Linear Programming"

DATE: December 8, 2008
TIME: 10:30 am
SPEAKER: Ashutosh Mahajan, Lehigh University
LOCATION: Building 221 Conference Room A216, Argonne National Laboratory
HOST: Sven Leyffer

Description:
Branch-and-cut algorithms have been the most successful in solving general Mixed Integer Linear Programs (MILPs). Branching or dividing the search space of the problem by using a disjunction is an important component of these algorithms. Existing methods select such disjunctions from a small set of candidates (usually variable disjunctions). We consider generalizations in which the candidates are drawn from a more general set. We first show that
the problem of selecting an optimal such disjunction can be formulated as a mathematical program. We also study the computational complexity of this problem and its variants and show that these are NP-hard. Our computational experiments show that using such disjunctions can result in a significant reduction in the size of the search tree. These results provide a strong motivation to develop fast heuristics for this problem. The results on the computational complexity are then extended to the problem of generating an "optimal" split inequality and to that of deciding if a given inequality is an elementary split inequality. This work was jointly done with Dr. Ted Ralphs at Lehigh University.

Save the event to your calendar [schedule.ics]