Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

This paper investigates linear programming based branch-and-bound using general disjunctions, also known as stabbing planes, for solving integer programs. We derive the first sub-exponential lower bound (in the encoding length L of the integer program) for the size of a general branch-and-bound tree for a particular class of (compact) integer programs, namely 2(Omega(L1/12-epsilon)) for every epsilon > 0. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation, which allows us to utilize sub-exponential lower-bounds for monotone real circuits separating the so-called clique-coloring pair. The same ideas also prove that refuting Theta(log(n))-CNFs requires size 2(n Omega(1)) branch-and-bound trees with high probability by considering the closely related notion of infeasibility certificates introduced by Hrube.s and Pudlak [18]. One important ingredient of the proof of our interpolation result is that for every general branch-and-bound tree proving integer-freeness of a product P x Q of two polytopes P and Q, there exists a closely related branch-and-bound tree for showing integer-freeness of P or one showing integer-freeness of Q. Moreover, we prove that monotone real circuits can perform binary search efficiently.