Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems

Mehran Poursoltani () and Erick Delage ()
Additional contact information
Mehran Poursoltani: GERAD & Department of Decision Sciences, HEC Montréal, Montreal, Quebec H3T 2A7, Canada
Erick Delage: GERAD & Department of Decision Sciences, HEC Montréal, Montreal, Quebec H3T 2A7, Canada

Operations Research, 2022, vol. 70, issue 5, 2906-2930

Abstract: This paper explores the idea that two-stage worst-case regret minimization problems with either objective or right-hand side uncertainty can be reformulated as two-stage robust optimization problems and can therefore benefit from the solution schemes and theoretical knowledge that have been developed in the last decade for this class of problems. In particular, we identify conditions under which a first-stage decision can be obtained either exactly using popular adjustable robust optimization decomposition schemes or approximately by conservatively using affine decision rules. Furthermore, we provide both numerical and theoretical evidence that, in practice, the first-stage decision obtained using affine decision rules is of high quality. Initially, this is done by establishing mild conditions under which these decisions can be proven exact, which effectively extends the space of regret minimization problems known to be solvable in polynomial time. We further evaluate both the suboptimality and computational efficiency of this tractable approximation scheme in a multi-item newsvendor problem and a production transportation problem.

Keywords: Optimization; two-stage robust optimization; regret minimization; affine decision rules (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2159 (application/pdf)

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:inm:oropre:v:70:y:2022:i:5:p:2906-2930

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().