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(L^{1/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. One important ingredient of the proof is that for every general branch-and-bound tree proving integer-freeness of a product $P\times 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