Distributionally Robust Linear and Discrete Optimization with Marginals
Date:
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 provide a primal-dual formulation for this problem. Though the robust bound is NP-hard, 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. We present the Distributionally Robust Max-Flow problem to illustrate our theoretical results.