Single-commodity network design with random edge capacities

► We study the single-commodity network design problem with stochastic edge capacities. ► We study structures of the optimal network designs. ► We compare structures arising from stochastic and deterministic problems. ► We characterize robust network designs. ► Our results provide a heuristic for the stochastic problem.