Distributionally Robust Linear and Discrete Optimization with Marginals.

Chen, Louis; Ma, Will; Natarajan, Karthik; Simchi-Levi, David; Yan, Zhenzhen

In optimization problems, decisions are often made in the face of uncertainty that might arise in the form of random costs or benefits. In "Distributionally Robust Linear and Discrete Optimization with Marginals," Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, and Zhenzhen Yan study a robust bound of linear and discrete optimization problems in which the objective coefficients are random and the set of admissible joint distributions is assumed to be specified only up to the marginals. They provide a primal-dual formulation for this problem, and in the process, unify existing results with new results. They 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. 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.

ADMISSIBLE sets; RANDOM sets; POLYTOPES; NP-hard problems; COST effectiveness

Operations Research, 2022, Vol 70, Issue 3, p1822

1526-5463

Academic Journal

10.1287/opre.2021.2243