Scenario consensus algorithms for solving stochastic and dynamic problems

Felipe Lagos ()
Additional contact information
Felipe Lagos: Universidad Adolfo Ibáñez

Journal of Global Optimization, 2025, vol. 93, issue 1, No 6, 175-213

Abstract: Abstract 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.

Keywords: Mixed-integer stochastic programming; Dynamic and stochastic transportation problems; Progressive hedging algorithm; Consensus functions (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01531-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01531-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01531-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().