Distributionally Robust Linear and Discrete Optimization with Marginals

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.