论文标题
可靠网络设计的离散和多面体不确定性集的比较
A Comparison of Discrete and Polyhedral Uncertainty Sets for Robust Network Design
论文作者
论文摘要
我们考虑了一个网络设计和扩展问题，我们现在需要进行能力投资，以便不确定的未来需求可以尽可能地满足。要使用强大的优化方法，我们需要构建一个不确定性集，其中包含所有我们认为可能可能发生的情况。在本文中，我们讨论了如何使用现实世界数据构建两种常见的不确定性集，它们是离散和多面体不确定性的。我们采用聚类来生成离散的不确定性集，并顺序放置超平面以生成多面体不确定性集。然后，我们比较了现实世界中这两种类型的模型所得强的解决方案的性能。我们的结果表明，在最近的网络设计文献中流行的多面体模型在计算负担和解决方案质量方面相对于所考虑的性能度量而言，效果不如离散模型。
We consider a network design and expansion problem, where we need to make a capacity investment now, such that uncertain future demand can be satisfied as closely as possible. To use a robust optimization approach, we need to construct an uncertainty set that contains all scenarios that we believe to be possible. In this paper we discuss how to construct two common types of uncertainty sets, which are discrete and polyhedral uncertainty, using real-world data. We employ clustering to generate a discrete uncertainty set, and place hyperplanes sequentially to generate a polyhedral uncertainty set. We then compare the performance of the resulting robust solutions for these two types of models on real-world data. Our results indicate that polyhedral models, while being popular in the recent network design literature, are less effective than discrete models both in terms of computational burden and solution quality with respect to the performance measure considered.
