Distributionally Robust Linear and Discrete Optimization with Marginals
Published in Accepted 10/18/21 (Operations Research), 2021
Recommended citation: Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, Zhenzhen Yan. (2021). "Distributionally Robust Linear and Discrete Optimization with Marginals." Operations Research. https://pubsonline.informs.org/doi/10.1287/opre.2021.2243
In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is shown to be NP-hard to compute for linear optimization problems, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss.
Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, Zhenzhen Yan. (2021). “Distributionally Robust Linear and Discrete Optimization with Marginals.” submitted.