Lattice basis reduction and mixed integer convex programming

It is well known that solving general integer programs is NP-hard [ 248]. Most current state-of-the-art commercial software implements traditional linear/nonlinear programming based branch-and-bound method or its variants. In the worst case this method, branching on one or more fractional variables generates a search tree with an exponential number of nodes in the input size of the problem. In 1983 Lenstra [198] proposed an algorithm of branching on hyperplanes for solving mixed integer linear programming problems. His seminal theoretical result shows that the proposed algorithm can solve general mixed integer linear programming problem in polynomial time in the input size of the problem with fixed number of integer variables. However, his algorithm finds limited value in practice.; In this thesis, we propose generalized branching methods for solving mixed integer linear programs. Our approach integrates the recent developments in the interior point methods and lattice basis reduction techniques. Special attention is paid to the problem of finding good branching hyperplanes. We show that the problem of finding a good branching hyperplane can be formulated as a shortest lattice vector finding problem on the adjoint lattice of the Kernel lattice of the equality constraints. Basis reduction techniques are employed to solve the shortest lattice vector problem. We show that the reduced adjoint lattice basis available at the root node can be used to bound the total number of nodes in the branch-and-bound tree. Implementation issues are discussed and computational results are presented on a set of hard pure integer linear programs.; We also present a primal-dual interior point algorithm with higher order corrections, which can be used to solve the analytic center finding problem. Convergence conditions for this algorithm are introduced and a Krylov subspace based higher order correction is proposed. Numerical results on the Netlib problems are presented to show that this method is attractive for solving hard linear programming problems.; In addition, we present our improvement on the complexity of the well known LLL lattice basis reduction algorithm. Our segment LLL algorithm with modular arithmetic combines segment idea [183] and modular arithmetic [276]. It gives an O(n 1.5) improvement over the LLL algorithm [199].