\(\)
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.
Moreover, this also implies 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 Hrubes and Pudlák.
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.
Article
View Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation