ON THE COMPLEXITY OF MIXED INTEGER PROGRAMMING

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.