Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation
Max Gläser, Marc E. Pfetsch · Society for Industrial and Applied Mathematics eBooks · 2024
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Ω(L1/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 lower-bounds for monotone real circuits separating the so-called clique-coloring pair. The same ideas also prove that refuting Θ(log(n))-CNFs requires size 2nΩ(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 integer-freeness of P or one showing integer-freeness of Q. Moreover, we prove that monotone real circuits can perform binary search efficiently.