  Problem definition: We study efficient exact solution approaches to solve
chance-constrained multicommodity network design problems under demand
uncertainty, an important class of network design problems. The chance
constraint requires us to construct a network that meets future commodity
demand sufficiently often, which makes the problem challenging to solve.
Methodology/results: We develop a solution approach based on Benders'
decomposition, and accelerate the approach with valid inequalities and cut
strengthening. We particularly investigate the effects of different subproblem
formulations on the strength of the resulting feasibility cuts. We propose a
new formulation that we term FlowMIS, and investigate its properties.
Additionally, we numerically show that FlowMIS outperforms standard
formulations: in our complete solution approach with all enhancements enabled,
FlowMIS solves 67 out of 120 solved instances the fastest, with an average
speed-up of 2.0x over a basic formulation. Implications: FlowMIS generates
strong feasibility cuts tailored to subproblems with a network flow structure.
This results in reduced solution times for existing decomposition-based
algorithms in the context of network design, and the ability to solve larger
problems.
