ISBN 9783843955300

978-3-8439-5530-0, Reihe Mathematik

Maximillian Gläser
On the Proof Complexity of Linear Programming Based Branch-and-Bound

171 Seiten, Dissertation Technische Universität Darmstadt (2024), Softcover, B5

Zusammenfassung / Abstract

This thesis investigates the proof system associated to the branch-and-bound method for linear integer programming, that is, we treat branch-and-bound trees as proofs of the integer-freeness of certain polyhedra (equivalently, of the infeasibility of integer linear programs). We treat both the proof system resulting from branch-and-bound branching on variable disjunctions as well as the one resulting from branching on general disjunctions.

We investigate lower bounds for these proof systems, their automatizability and the complexity of estimating the minimum required size of a tree. In particular, we derive the first super-polynomial lower bound for branch-and-bound using general disjunctions via interpolation.