TY - GEN

T1 - Branch-and-bound solves random binary IPS in polytime

AU - Dey, Santanu S.

AU - Dubey, Yatharth

AU - Molinaro, Marco

N1 - Funding Information:
∗S.S.D.was partiallysupportedbyONRundergrantNo. N4458-NV-ONRandM.Mwas partiallysupportedbytheCoor-denacão deAperfeicoamento dePessoal deNívelSuperior-Brasil (CAPES)-FinanceCode001,CNPqBolsadeProdutividadeem Pesquisa #4310516/2017-0 and FAPERJ grant Jovem Cientista doNossoEstado.
Funding Information:
S. S. D. was partially supported by ONR under grant No. N4458-NV-ONR and M. M was partially supported by the Coordenac?o de Aperfeicoamento de Pessoal de N?vel Superior - Brasil (CAPES) - Finance Code 001, CNPq Bolsa de Produtividade em Pesquisa #4310516/2017-0 and FAPERJ grant Jovem Cientista do Nosso Estado.
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

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 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.

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 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.

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

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

M3 - Conference contribution

AN - SCOPUS:85104224744

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 579

EP - 591

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -