  Network design problems involve constructing edges in a transportation or
supply chain network to minimize construction and daily operational costs. We
study a stochastic version where operational costs are uncertain due to
fluctuating demand and estimated as a sample average from historical data. This
problem is computationally challenging, and instances with as few as 100 nodes
often cannot be solved to optimality using current decomposition techniques. We
propose a stochastic variant of Benders decomposition that mitigates the high
computational cost of generating each cut by sampling a subset of the data at
each iteration and nonetheless generates deterministically valid cuts, rather
than the probabilistically valid cuts frequently proposed in the stochastic
optimization literature, via a dual averaging technique. We implement both
single-cut and multi-cut variants of this Benders decomposition, as well as a
variant that uses clustering of the historical scenarios. To our knowledge,
this is the first single-tree implementation of Benders decomposition that
facilitates sampling. On instances with 100-200 nodes and relatively complete
recourse, our algorithm achieves 5-7% optimality gaps, compared with 16-27% for
deterministic Benders schemes, and scales to instances with 700 nodes and 50
commodities within hours. Beyond network design, our strategy could be adapted
to generic two-stage stochastic mixed-integer optimization problems where
second-stage costs are estimated via a sample average.
