Recoverable Robustness by Column Generation
Recoverable Robustness by Column Generation
复制标题
通过柱生成恢复稳健性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H. Hoogeveen
中科院分区：
文献类型：
--
作者：
M. Akker;P. Bouman;H. Hoogeveen
现实生活中的规划问题往往是复杂的干扰的发生，这意味着原来的计划不能再遵循，必须采取一些恢复行动，以科普干扰。在这种情况下，武装自己对付一般的动乱是值得的。众所周知的方法来创建计划，考虑可能的，常见的干扰是鲁棒优化和随机规划。最近，一种新的方法已经开发出来，结合了这两个最好的：可恢复的鲁棒性。在本文中，我们应用列生成技术，找到解决方案，可恢复的鲁棒性问题。我们考虑两种类型的解决方案的方法：单独恢复和联合恢复。我们展示了我们的方法上的两个例子问题：大小鲁棒背包问题，其中背包的大小可能会减少，和需求鲁棒最短路径问题，其中水槽是不确定的，边缘的成本可能会增加。
Real-life planning problems are often complicated by the occurrence of disturbances, which imply that the original plan cannot be followed anymore and some recovery action must be taken to cope with the disturbance. In such a situation it is worthwhile to arm yourself against common disturbances. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. Recently, a new approach has been developed that combines the best of these two: recoverable robustness. In this paper, we apply the technique of column generation to find solutions to recoverable robustness problems. We consider two types of solution approaches: separate recovery and combined recovery. We show our approach on two example problems: the size robust knapsack problem, in which the knapsack size may get reduced, and the demand robust shortest path problem, in which the sink is uncertain and the cost of edges may increase.