\(\)

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