Optimization Online


Supermodularity in Two-Stage Distributionally Robust Optimization

Daniel Zhuoyu Long (zylong***at***se.cuhk.edu.hk)
Jin Qi (jinqi***at***ust.hk)
Aiqi Zhang (aqzhang***at***se.cuhk.edu.hk)

Abstract: In this paper, we solve a class of two-stage distributionally robust optimization problems which have the property of supermodularity. We exploit the explicit upper bounds on the expectation of supermodular functions and derive the worst-case distribution for the robust counterpart. This enables us to develop an efficient method to derive an exact optimal solution of these two-stage problems. Further, we provide a necessary and sufficient condition to check whether any given two-stage optimization problem has supermodularity. We apply this framework to classic problems, including the multi-item newsvendor problem, the appointment scheduling problem and general assemble-to-order (ATO) systems. While these problems are typically computationally challenging, they can be solved efficiently using our approach.

Keywords: distributionally robust optimization; two-stage problems; supermodularity

Category 1: Applications -- OR and Management Sciences

Category 2: Robust Optimization

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

Citation: Long, Qi, Zhang (2019), The Chinese University of Hong Kong, working paper

Download: [PDF]

Entry Submitted: 11/06/2019
Entry Accepted: 11/06/2019
Entry Last Modified: 04/15/2021

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