Lower bounds on the size of general branch-and-bound trees

Santanu S. Dey, Yatharth Dubey, Marco Molinaro

Research output: Contribution to journalArticlepeer-review

Abstract

A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form π⊤x≤π0∨π⊤x≥π0+1, where π is an integer vector and π is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the size of general branch-and-bound trees persists even when we add Gaussian noise to the coefficients of the cross-polytope, thus showing that a polynomial-size “smoothed analysis” upper bound is not possible. The results in this paper can be viewed as the branch-and-bound analog of the seminal paper by Chvátal et al. (Linear Algebra Appl 114:455–499, 1989), who proved lower bounds for the Chvátal–Gomory rank.

Original languageEnglish (US)
Pages (from-to)539-559
Number of pages21
JournalMathematical Programming
Volume198
Issue number1
DOIs
StatePublished - Mar 2023
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds on the size of general branch-and-bound trees'. Together they form a unique fingerprint.

Cite this