On generalized branching methods for mixed integer programming

Sanjay Mehrotra (mehrotraiems.northwestern.edu)
Zhifeng Li (zhifengiems.northwestern.edu)

Abstract: In this paper we present a restructuring of the computations in Lenstra's methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an 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\'{a}sz (LLL) \cite{LLL82} or the generalized basis reduction algorithm of Lov\'{a}sz and Scarf \cite{LS92} are described in the space of original variables. Based on these results we give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra \cite{AL02}. We show that the reduced basis available at the root node has useful information on the branching hyperplanes for the generalized branch-and-bound tree. Based on these results algorithms are also given for solving mixed convex integer programs.

Keywords: Mixed integer programming, branching on hyperplanes, lattice basis reduction, interior point methods, semidefinite programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation:

Download: [PDF]

Entry Submitted: 01/01/2005
Entry Accepted: 01/02/2005
Entry Last Modified: 01/01/2005

Modify/Update this entry