  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.
