Distributionally Robust Linear and Discrete Optimization with Marginals
研究了目标系数随机且仅知边际分布时的线性与离散优化问题，给出了原对偶公式，证明了计算一般多面体下界的NP困难性，并识别了可高效计算的两类充分条件。
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.