Amitabh Basu, Johns Hopkins University

Abstract

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on variable disjunctions. In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.