Algorithms and Cutting Planes for Mixed Integer Programs

Abstract

This dissertation is devoted to solving general mixed integer optimization problems. Our main focus is understanding and developing strong cutting planes for mixed integer linear programs through Gomory and Johnson's k-dimensional infinite group relaxation. Each cut generated from this problem has an associated function, and among the strongest are extreme functions. For k=1 , we give an algorithm for testing the extremality of piecewise linear (possibly discontinuous) functions with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We extend this algorithm to a large class of functions for k = 2 and develop theory for a more general result for k ≥ 2. For the k-dimensional infinite group relaxation, we prove that any minimal valid function that is continuous piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuéjols and Molinaro for k=2.

We also contribute to the understanding of cutting plane closures for mixed integer programs. Cutting planes derived from maximal lattice-free convex sets have recently been studied intensely by the integer programming community. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel, and later by Averkov, some basic questions remain unresolved. We show that when the number of integer variables is two the triangle closure is a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of our proof are also used to refine Cornuéjols and Margot's necessary conditions identifying valid inequalities as facet-defining and to obtain polynomial complexity results concerning the mixed integer hull.

Finally, we study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm, which is attributed to Heinz. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. Our algorithm achieves a time-complexity of 2^{2nlog₂(n) + O(n)} in terms of the dimension n.