Efficient Solution Selection for Two-stage Stochastic Programs

Xin Fei*, Nalân Gülpınar, Jürgen Branke

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)

Abstract

Sampling-based stochastic programs are extensively applied in practice. However, the resulting models tend to be computationally challenging. A reasonable number of samples needs to be identified to represent the random data, and a group of approximate models can then be constructed using such a number of samples. These approximate models can produce a set of potential solutions for the original model. In this paper, we consider the problem of allocating a finite computational budget among numerous potential solutions of a two-stage linear stochastic program, which aims to identify the best solution among potential ones by conducting simulation under a given computational budget. We propose a two-stage heuristic approach to solve the computational resource allocation problem. First, we utilise a Wasserstein-based screening rule to remove potentially inferior solutions from the simulation. Next, we use a ranking and selection technique to efficiently collect performance information of the remaining solutions. The performance of our approach is demonstrated through well-known benchmark problems. Results show that our method provides good trade-offs between computational effort and solution performance.
Original languageEnglish
Pages (from-to)918-929
JournalEuropean Journal of Operational Research
Volume277
Issue number3
Early online date12 Feb 2019
DOIs
Publication statusE-pub ahead of print - 12 Feb 2019

Fingerprint Dive into the research topics of 'Efficient Solution Selection for Two-stage Stochastic Programs'. Together they form a unique fingerprint.

Cite this