Problem-driven scenario clustering in stochastic optimization

Julien Keutchayan (), Janosch Ortmann () and Walter Rei ()
Additional contact information
Julien Keutchayan: McGill University
Janosch Ortmann: UQAM
Walter Rei: UQAM

Computational Management Science, 2023, vol. 20, issue 1, No 13, 33 pages

Abstract: Abstract In stochastic optimisation, the large number of scenarios required to faithfully represent the underlying uncertainty is often a barrier to finding efficient numerical solutions. This motivates the scenario reduction problem: by finding a smaller subset of scenarios, reduce the numerical complexity while keeping the error at an acceptable level. In this paper we propose a novel and computationally efficient methodology to tackle the scenario reduction problem for two-stage problems when the error to be minimised is the implementation error, i.e. the error incurred by implementing the solution of the reduced problem in the original problem. Specifically, we develop a problem-driven scenario clustering method that produces a partition of the scenario set. Each cluster contains a representative scenario that best reflects the optimal value of the objective function in each cluster of the partition to be identified. We demonstrate the efficiency of our method by applying it to two challenging two-stage stochastic combinatorial optimization problems: the two-stage stochastic network design problem and the two-stage facility location problem. When compared to alternative clustering methods and Monte Carlo sampling, our method is shown to clearly outperform all other methods.

Keywords: Stochastic optimization; Scenario reduction; Problem-driven scenario clustering (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10287-023-00446-2 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:comgts:v:20:y:2023:i:1:d:10.1007_s10287-023-00446-2

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-023-00446-2

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().