论文标题
数值方法，用于具有边缘约束的两阶段分布的大约最佳解决方案
Numerical method for approximately optimal solutions of two-stage distributionally robust optimization with marginal constraints
论文作者
论文摘要
我们考虑一般的两阶段分配方面可靠的优化（DRO）问题，其中包括诸如任务计划，汇编系统和供应链网络设计等突出实例。模棱两可的集合受到不一定是离散的固定边缘分布的约束。我们开发了一种数值算法，用于计算此类问题的大致最佳解决方案。通过通过有限的线性约束来代替边际约束，我们得出了DRO问题的放松，该问题是其上限。我们可以控制放松误差，任意接近0。我们发展二元性结果并将INF-SUP问题转化为INF-INF问题。这导致了针对边缘约束的两阶段DRO问题的数值算法，该算法解决了线性半无限优化问题。除了大约最佳的解决方案外，该算法还计算出最佳问题的上限和下限。计算边界之间的差异提供了计算解决方案的直接次数估计。最重要的是，人们可以选择算法的输入，从而将子临时性控制为任意小。在我们的数值示例中，我们将提出的算法应用于任务计划，汇编系统和供应链网络设计。这些问题中的歧义设置涉及大量边际，其中包括离散和连续分布。数值结果表明，所提出的算法计算出高质量的鲁棒决策及其相应的亚Xipimality估计，实际上并非过分保存。
We consider a general class of two-stage distributionally robust optimization (DRO) problems which includes prominent instances such as task scheduling, the assemble-to-order system, and supply chain network design. The ambiguity set is constrained by fixed marginal distributions that are not necessarily discrete. We develop a numerical algorithm for computing approximately optimal solutions of such problems. Through replacing the marginal constraints by a finite collection of linear constraints, we derive a relaxation of the DRO problem which serves as its upper bound. We can control the relaxation error to be arbitrarily close to 0. We develop duality results and transform the inf-sup problem into an inf-inf problem. This leads to a numerical algorithm for two-stage DRO problems with marginal constraints which solves a linear semi-infinite optimization problem. Besides an approximately optimal solution, the algorithm computes both an upper bound and a lower bound for the optimal value of the problem. The difference between the computed bounds provides a direct sub-optimality estimate of the computed solution. Most importantly, one can choose the inputs of the algorithm such that the sub-optimality is controlled to be arbitrarily small. In our numerical examples, we apply the proposed algorithm to task scheduling, the assemble-to-order system, and supply chain network design. The ambiguity sets in these problems involve a large number of marginals, which include both discrete and continuous distributions. The numerical results showcase that the proposed algorithm computes high-quality robust decisions along with their corresponding sub-optimality estimates with practically reasonable magnitudes that are not over-conservative.
