Two-stage stochastic integer programs provide a powerful framework for modeling
decision-making under uncertainty, but they are notoriously difficult to solve at
scale due to their high dimensionality and intrinsic nonconvexity.
Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual
decomposition methods) have become standard computational approaches for such
problems and demonstrate excellent empirical performance in practice.
Despite their widespread use, however, existing theoretical guarantees are almost
exclusively based on worst-case analyses, which predict exponential convergence
behavior in the problem dimension and fail to explain the strong performance
observed in practice. In this paper, we present the first average-case analysis of Branch-and-Price
for a broad class of two-stage stochastic binary integer programs.
We study a stochastic-input model in which objective coefficients and constraint
matrices are drawn at random and right-hand-side vectors scale with the decision
dimension, while the number of constraints per scenario is fixed.
Under this model, we prove that, with high probability, Branch-and-Price explores
at most \( n^{O(\log s)} \) nodes, yielding a quasi-polynomial bound on the size of
the search tree in typical instances, where \( n \) denotes the decision dimension
and \( s \) the number of scenarios. A key ingredient of our analysis is an average-case bound on the integrality gap of
the natural linear programming (LP) relaxation. We show that this gap shrinks at a rate
\( O\!\left(\frac{\log s \log^2 n}{n}\right) \) with high probability. This result is of
independent interest, as it implies that the integrality gap grows only logarithmically
with the number of scenarios on average. This helps explain why LP-based
heuristics work well in practice, even in large-scale stochastic settings with an enormous number of
scenarios, where LP relaxations with a large number of constraints are usually believed to be weak.