COLLEGE OF ARTS AND SCIENCES Department of Mathematics and Statistics
(click here for colloquia)

Colloquium:On Generalized Branching Methods for Mixed Integer Programming


4:10 p.m. Neill Hall 5W

Zhifeng Li

Abstract: We present a fundamental restructuring of computations in Lenstra's methods for solving mixed integer linear program. We show that the problem of finding a good branching hyperplane can be formulated as a short lattice vector finding problem on the adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short lattice vector finding algorithms, such as Lenstra, Lenstra, Lovász (LLL) or the generalized basis reduction algorithm (GBR) of Lovász and Scarf are described in the space of original variables. In the context of LLL (and related) algorithms the computations are now performed using projection matrices similar to those appearing in interior point methods for continuous optimization. Based on these results we also give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra. Computational results are presented on a set of pure integer linear programs that are difficult to solve by standard branch-and-cut approaches. We also extend our discussion to the mixed integer case. (This is a part of my dissertation work directed by Professor Sanjay Mehrotra)