TY - JOUR

T1 - Branch-and-bound solves random binary IPs in poly(n)-time

AU - Dey, Santanu S.

AU - Dubey, Yatharth

AU - Molinaro, Marco

N1 - Funding Information:
We are extremely grateful to Daniel Dadush for suggesting several improvements to the paper. Santanu S. Dey would like to gratefully acknowledge the support given by the Airforce office of scientific research, award number FA9550-22-1-0052. Marco Molinaro was supported in part by the Coordenaccão de Aperfeiccoamento de Pessoal de Nível Superior (CAPES, Brasil) - Finance Code 001, by Bolsa de Produtividade em Pesquisa 12751/2021-4 from CNPq, FAPERJ grant “Jovem Cientista do Nosso Estado”, and by the CAPES-PrInt program.
Publisher Copyright:
© 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2023/6

Y1 - 2023/6

N2 - 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 via disjunctions of the form xj≤ ⌊ x¯ j⌋ ∨ xj≥ ⌈ x¯ j⌉ , where x¯ is an optimal solution to the LP corresponding to the parent 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 an indication as to why branch-and-bound with variable branching works so well in practice.

AB - 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 via disjunctions of the form xj≤ ⌊ x¯ j⌋ ∨ xj≥ ⌈ x¯ j⌉ , where x¯ is an optimal solution to the LP corresponding to the parent 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 an indication as to why branch-and-bound with variable branching works so well in practice.

UR - http://www.scopus.com/inward/record.url?scp=85140121916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85140121916&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01895-4

DO - 10.1007/s10107-022-01895-4

M3 - Article

AN - SCOPUS:85140121916

SN - 0025-5610

VL - 200

SP - 569

EP - 587

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -