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.
Citation
S. Mehrotra and Z. Li (2010), "Branching on Hyperplane Methods for Mixed Integer Linear and Convex Programming Using Adjoint Lattices" Journal of Global Optimization, DOI: 10.1007/s10898-010-9554-4
Article
View On generalized branching methods for mixed integer programming