论文标题
通过量化整数编程进行多阶段鲁棒分散优化
Multistage Robust Discrete Optimization via Quantified Integer Programming
论文作者
论文摘要
决策需要考虑不确定的环境。在过去的几十年中，强大的优化已成为一种杰出的方法，可以生产出对不确定性进行免疫的溶液。强大离散优化的主要重点是对单个或两个阶段问题的分析和解决方案，在这种情况下，决策者对解决方案部分后获得的其他知识的反应有限。由于其计算困难，两个阶段以外的多阶段问题受到了较少的关注。 在本文中，我们认为可以通过量化整数程序的镜头来看到多阶段鲁棒的离散问题，在该程序中，已经开发出了减少搜索树大小的强大工具。通过制定整数和量化的整数编程公式，可以比较两者中最先进的求解器的性能。使用选择，分配，批号和背包问题作为测试床，我们表明，在合理时间内可以解决多达九个阶段的问题。
Decision making needs to take an uncertain environment into account. Over the last decades, robust optimization has emerged as a preeminent method to produce solutions that are immunized against uncertainty. The main focus in robust discrete optimization has been on the analysis and solution of one- or two-stage problems, where the decision maker has limited options in reacting to additional knowledge gained after parts of the solution have been fixed. Due to its computational difficulty, multistage problems beyond two stages have received less attention. In this paper we argue that multistage robust discrete problems can be seen through the lens of quantified integer programs, where powerful tools to reduce the search tree size have been developed. By formulating both integer and quantified integer programming formulations, it is possible to compare the performance of state-of-the-art solvers from both worlds. Using selection, assignment, lot-sizing and knapsack problems as a testbed, we show that problems with up to nine stages can be solved to optimality in reasonable time.
