Supermodularity in Two-Stage Distributionally Robust Optimization
研究具有超模性的两阶段分布鲁棒优化问题，利用超模函数的最坏情况期望推导出鲁棒对偶的最坏分布，从而高效求解多物品报童、设施选址等经典问题，并提供超模性判据。
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. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the National Natural Science Foundation of China [Grant 71971187], and Hong Kong Research Grants Council [Collaborative Research Fund (C6103-20GF), General Research Fund (14210821, 16204521, 16212419)]. Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.4748 .