Optimization Online


Scenario Consensus Algorithms for Solving Stochastic and Dynamic Problems

Felipe Lagos (felipe.lagos***at***uai.cl)

Abstract: In transportation problems and in 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), that has been proved effective for transportation problems, but it does not provide flexibility for finding solutions that take into account all the uncertainty of the problem. Alternative approaches for solving problems with finite number of scenarios are the Progressive Hedging Algorithm (PHA) and the Subgradient Algorithm (SA). The similarity between PHA and SA are many, 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, for which we provide theoretical guarantees that helps to understand both this algorithm and the PHA from a new point of view. In addition, we propose a DPHA-based Heuristic (DPHH), and show optimality guarantees for the solution obtained. Then, we present the MSA and the SA with consensus functions. Our analysis allows us to highlight 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 study 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 Scenario Consensus Algorithms (SCA).

Keywords: mixed-integer stochastic programming, progressive hedging, lagrangian duality, consensus functions

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 08/20/2021
Entry Accepted: 08/20/2021
Entry Last Modified: 08/27/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society