Convex approximations of two-stage risk-averse mixed-integer recourse models

E. Ruben van Beesten*, Ward Romeijnders, Kees Jan Roodbergen

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Downloads (Pure)

Abstract

We consider two-stage risk-averse mixed-integer recourse models with law invariant coherent risk measures. As in the risk-neutral case, these models are generally non-convex as a result of the integer restrictions on the second-stage decision variables and hence, hard to solve. To overcome this issue, we propose a convex approximation approach. We derive a performance guarantee for this approximation in the form of an asymptotic error bound, which depends on the choice of risk measure. This error bound, which extends an existing error bound for the conditional value at risk, shows that our approximation method works particularly well if the distribution of the random parameters in the model is highly dispersed. For special cases we derive tighter, non-asymptotic error bounds. Whereas our error bounds are valid only for a continuously distributed second-stage right-hand side vector, practical optimization methods often require discrete distributions. In this context, we show that our error bounds provide statistical error bounds for the corresponding (discretized) sample average approximation (SAA) model. In addition, we construct a Benders’ decomposition algorithm that uses our convex approximations in an SAA-framework and we provide a performance guarantee for the resulting algorithm solution. Finally, we perform numerical experiments which show that for certain risk measures our approach works even better than our theoretical performance guarantees suggest.
Original languageEnglish
Pages (from-to)313-347
Number of pages25
JournalComputational optimization and applications
Volume88
Early online date13-Feb-2024
DOIs
Publication statusPublished - May-2024

Fingerprint

Dive into the research topics of 'Convex approximations of two-stage risk-averse mixed-integer recourse models'. Together they form a unique fingerprint.

Cite this