Optimization Online


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

Mehran Poursoltani (mehran.poursoltani***at***hec.ca)
Erick Delage (erick.delage***at***hec.ca)

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 employing 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 proved exact, which effectively extends the space of regret minimization problems known to be solvable in polynomial time. We further evaluate both the sub-optimality and computational efficiency of this tractable approximation scheme in a multi-item newsvendor problem and a production transportation problem.

Keywords: regret minimization, robust optimization, newsvendor problem, affine decision rules

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 07/22/2019
Entry Accepted: 07/22/2019
Entry Last Modified: 07/10/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society