ON THE COMPLEXITY OF MIXED INTEGER PROGRAMMING

Embargo until
Date
2021-06-28
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
We study the theoretical complexity of mixed integer programming algorithms. We first discuss the relative efficiency of branch and bound (BB) and cutting plane (CP) algorithms in different scenarios. We made the comparisons based on two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. Next, we explain the empirically observed phenomenon, from a theoretical perspective, that combining BB and CP into a branch-and-cut (BC) framework can be orders of magnitude more efficient than applying CP or BB on their own. Specifically, we give general conditions under which a BC scheme gives provably exponential advantage in efficiency. We also develop a new polynomial time cutting plane algorithm based on split cuts to solve integer programs in two-dimensional space. In addition, we show that one can use branching to enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero subdeterminants, in time polynomial in the dimension and encoding size of the polytope.
Description
Keywords
Mixed integer programming, complexity
Citation