Optimization Online


On generalized branching methods for mixed integer programming

Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)
Zhifeng Li (zhifeng***at***iems.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society