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 subexponential 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 Ω(L 1/12-ǫ ) for every ǫ > 0. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation, which allows us to utilize sub-exponential lowerbounds for monotone real circuits separating the so-called clique-coloring pair. Moreover, this also implies that refuting Θ(log(n))-CNFs requires size 2 n Ω(1) branch-and-bound trees with high probability by considering the closely related notion of infeasibility certificates introduced by Hrubeš and Pudlák [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 × Q of two polytopes P and Q, there exists a closely related branch-and-bound tree for showing integerfreeness of P or one showing integer-freeness of Q. Moreover, we prove that monotone real circuits can perform binary search efficiently.