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 条

[31] Distributionally Robust Optimization in Possibilistic Setting
Guillaume, Romain
Kasperski, Adam
Zielinski, Pawel
IEEE CIS INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS 2021 (FUZZ-IEEE), 2021,
[32] Distributionally Robust Optimization with Markovian Data
Li, Mengmeng
Sutter, Tobias
Kuhn, Daniel
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139, 2021, 139
[33] Distributionally Robust Bayesian Optimization with φ-divergences
Husain, Hisham
Vu Nguyen
van den Hengel, Anton
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 36 (NEURIPS 2023), 2023,
[34] Distributionally Robust Optimization with Data Geometry
Liu, Jiashuo
Wu, Jiayun
Li, Bo
Cui, Peng
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 35 (NEURIPS 2022), 2022,
[35] Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
Yannan Chen
Hailin Sun
Huifu Xu
Computational Optimization and Applications, 2021, 78 : 205 - 238
[36] Distributionally Robust Skeleton Learning of Discrete Bayesian Networks
Li, Yeshu
Ziebart, Brian D.
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 36 (NEURIPS 2023), 2023,
[37] Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
Chen, Yannan
Sun, Hailin
Xu, Huifu
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2021, 78 (01) : 205 - 238
[38] Distributionally Robust Optimization Under Distorted Expectations
Cai, Jun
Li, Jonathan Yu-Meng
Mao, Tiantian
OPERATIONS RESEARCH, 2023,
[39] Globalized distributionally robust optimization based on samples
Yueyao Li
Wenxun Xing
Journal of Global Optimization, 2024, 88 : 871 - 900
[40] Distributionally Robust Optimization and Generalization in Kernel Methods
Staib, Matthew
Jegelka, Stefanie
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), 2019, 32

← 1 2 3 4 5 →