Supermodularity in Two-Stage Distributionally Robust Optimization

• 成果类型: Article
• 署名作者: Long, Daniel Zhuoyu; Qi, Jin; Zhang, Aiqi
• 署名单位: Chinese University of Hong Kong; Hong Kong University of Science & Technology; Wilfrid Laurier University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.4748
• 发表日期: 2024
• 页码: 1394-1409
• 关键词: distributionally robust optimization; two-stage optimization; supermodularity; assemble-to-order

摘要

In this paper, we solve a class of two-stage distributionally robust optimization problems that have the property of supermodularity. We exploit the explicit worst case expectation of supermodular functions and derive the worst case distribution for the robust counterpart. This enables us to develop an efficient method to obtain an exact optimal solution to these two-stage problems. Further, we provide a necessary and sufficient condition for checking whether any given two-stage optimization problem has the supermodularity property. We also investigate the optimality of the segregated affine decision rules when problems have the property of supermodularity. We apply this framework to several classic problems, including the multi-item newsvendor problem, the facility location problem, the lot-sizing problem on a network, the appointment scheduling problem, and the assemble-to-order problem. Whereas these problems are typically computationally challenging, they can be solved efficiently under our assumptions. Finally, numerical examples are conducted to illustrate the effectiveness of our approach.