Distributionally Robust Linear and Discrete Optimization with Marginals

Louis Chen (), Will Ma (), Karthik Natarajan (), David Simchi-Levi () and Zhenzhen Yan ()
Additional contact information
Louis Chen: Operations Research Department, Naval Postgraduate School, Monterey, California 93943
Will Ma: Graduate School of Business, Columbia University, New York, New York 10027
Karthik Natarajan: Engineering Systems and Design, Singapore University of Technology and Design, Singapore 487372, Singapore
David Simchi-Levi: Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Zhenzhen Yan: School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore

Operations Research, 2022, vol. 70, issue 3, 1822-1834

Abstract: 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.

Keywords: Optimization; marginal distribution model; linear programming; duality; optimal transport (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2243 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:3:p:1822-1834

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().