Distributionally Robust Linear and Discrete Optimization with Marginals

• 成果类型: Article; Early Access
• 署名作者: Chen, Louis; Ma, Will; Natarajan, Karthik; Simchi-Levi, David; Yan, Zhenzhen
• 署名单位: United States Department of Defense; United States Navy; Naval Postgraduate School; Columbia University; Singapore University of Technology & Design; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Nanyang Technological University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2243
• 发表日期: 2022
• 页码: 1-13
• 关键词: marginal distribution model; linear programming; Duality; Optimal Transport

摘要

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.