Branch-and-bound solves random binary IPS in polytime

Santanu S. Dey, Yatharth Dubey, Marco Molinaro

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v+1 in the other node. Even though modern MILP solvers are able to solve very large-scale instances efficiently, relatively little attention has been given to understanding why the underlying branch-and-bound algorithm performs so well. In this paper our goal is to theoretically analyze the performance of the standard variable branching based branch-and-bound algorithm. In order to avoid the exponential worst-case lower bounds, we follow the common idea of considering random instances. More precisely, we consider random integer programs where the entries of the coefficient matrix and the objective function are randomly sampled. Our main result is that with good probability branch- and-bound with variable branching explores only a polynomial number of nodes to solve these instances, for a fixed number of constraints. To the best of our knowledge this is the first known such result for a standard version of branch- and-bound. We believe that this result provides a compelling indication of why branch-and-bound with variable branching works so well in practice.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781611976465
StatePublished - 2021
Externally publishedYes
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Branch-and-bound solves random binary IPS in polytime'. Together they form a unique fingerprint.

Cite this