Distributionally Robust Linear and Discrete Optimization with Marginals

被引：0
|
作者：
Chen L. [1 ]
Ma W. [2 ]
Natarajan K. [3 ]
Simchi-Levi D. [4 ]
Yan Z. [5 ]
机构：
[1] Operations Research Department, Naval Postgraduate School, Monterey, 93943, CA
[2] Graduate School of Business, Columbia University, New York, 10027, NY
[3] Engineering Systems and Design, Singapore University of Technology and Design, Singapore
[4] Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, Operations Research Center, Massachusetts Institute of Technology, Cambridge, 02139, MA
[5] School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
来源：
Operations Research | 2022年 / 70卷 / 03期
关键词：
duality; linear programming; marginal distribution model; optimal transport;
D O I：
10.1287/OPRE.2021.2243
中图分类号：
学科分类号：
摘要：
In this paper, we study linear and discrete optimization problems in which the objective coefficients are random, and the goal is to evaluate a robust bound on the expected optimal value, where the set of admissible joint distributions is assumed to be specified only up to the marginals. We study a primal-dual formulation for this problem, and in the process, unify existing results with new results. We establish NP-hardness of computing the bound for general polytopes and identify two sufficient conditions: one based on a dual formulation and one based on sublattices that provide a class of polytopes where the robust bounds are efficiently computable. We discuss several examples and applications in areas such as scheduling. Copyright © 2022 Informs.
引用
收藏
页码：1822 / 1834
页数：12
相关论文
共 50 条
  • [1] Distributionally Robust Linear and Discrete Optimization with Marginals
    Chen, Louis
    Ma, Will
    Natarajan, Karthik
    Simchi-Levi, David
    Yan, Zhenzhen
    OPERATIONS RESEARCH, 2022, : 1 - 13
  • [2] Discrete Approximation Scheme in Distributionally Robust Optimization
    Liu, Yongchao
    Yuan, Xiaoming
    Zhang, Jin
    NUMERICAL MATHEMATICS-THEORY METHODS AND APPLICATIONS, 2021, 14 (02): : 285 - 320
  • [3] Discrete Approximation and Quantification in Distributionally Robust Optimization
    Liu, Yongchao
    Pichler, Alois
    Xu, Huifu
    MATHEMATICS OF OPERATIONS RESEARCH, 2019, 44 (01) : 19 - 37
  • [4] Robust and Distributionally Robust Optimization Models for Linear Support Vector Machine
    Faccini, Daniel
    Maggioni, Francesca
    Potra, Florian A.
    COMPUTERS & OPERATIONS RESEARCH, 2022, 147
  • [5] Robust and Distributionally Robust Optimization Models for Linear Support Vector Machine
    Faccini, Daniel
    Maggioni, Francesca
    Potra, Florian A.
    Computers and Operations Research, 2022, 147
  • [6] Distributionally robust discrete optimization with Entropic Value-at-Risk
    Long, Daniel Zhuoyu
    Qi, Jin
    OPERATIONS RESEARCH LETTERS, 2014, 42 (08) : 532 - 538
  • [7] EFFICIENT ALGORITHMS FOR DISTRIBUTIONALLY ROBUST STOCHASTIC OPTIMIZATION WITH DISCRETE SCENARIO SUPPORT
    Zhang, Zhe
    Ahmed, Shabbir
    Lan, Guanghui
    SIAM JOURNAL ON OPTIMIZATION, 2021, 31 (03) : 1690 - 1721
  • [8] Nonlinear distributionally robust optimization
    Sheriff, Mohammed Rayyan
    Esfahani, Peyman Mohajerin
    MATHEMATICAL PROGRAMMING, 2024,
  • [9] Adaptive Distributionally Robust Optimization
    Bertsimas, Dimitris
    Sim, Melvyn
    Zhang, Meilin
    MANAGEMENT SCIENCE, 2019, 65 (02) : 604 - 618
  • [10] BAYESIAN DISTRIBUTIONALLY ROBUST OPTIMIZATION
    Shapiro, Alexander
    Zhou, Enlu
    Lin, Yifan
    SIAM JOURNAL ON OPTIMIZATION, 2023, 33 (02) : 1279 - 1304
12345