On the Proof Complexity of Linear Programming Based Branch-and-Bound

Beschreibung

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.

Autor*in

Maximillian Gläser

Themen in »On the Proof Complexity of Linear Programming Based Branch-and-Bound«

Integer Programming Branch-and-Bound Lineare und ganzahlige Programmierung

Stimmen zu »On the Proof Complexity of Linear Programming Based Branch-and-Bound«

Details

Link teilen