Scenario consensus algorithms for solving stochastic and dynamic problems

In transportation problems and many other planning problems, there are important sources of uncertainty that must be addressed to find effective and efficient solutions. A common approach for solving these dynamic and stochastic problems is the multiple scenario approach (MSA), which has been proven effective for transportation problems, but it does not provide flexibility for finding solutions that account for all the uncertainty of the problem. Alternative approaches for solving problems with a finite number of scenarios are the progressive hedging algorithm (PHA) and the subgradient algorithm (SA). There are many similarities between PHA and SA; however, there are some differences that lead them to have very different theoretical guarantees and performance. We present a new exact algorithm, the dynamic progressive hedging algorithm (DPHA), for which we provide theoretical guarantees that help to understand both this algorithm and the PHA from a new point of view. We also propose a DPHA-based heuristic (DPHH) and show optimality guarantees for the solution obtained. Our analysis highlights the advantages and disadvantages of the DPHA, the SA, and the MSA, which gives guidance for future research in choosing the proper method for the problem in hand. In a computational study, we consider the stochastic server location problem (SSLP) and the two-stage stochastic assignment and team-orienteering problem (TSSATOP), and we show the empirical performance of the proposed algorithms.