A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
复制标题
最小最大后悔优化中点解的新界限及其在鲁棒最短路径问题中的应用
DOI：
10.1016/j.ejor.2015.02.023
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Goerigk
中科院分区：
文献类型：
--
作者：
A. Chassein;M. Goerigk
最小最大遗憾优化的目的是找到鲁棒的解决方案，在最坏的情况下表现最好，相比各自的最佳目标值在每个场景。即使对于像盒子这样的简单不确定性集，大多数多项式可解的优化问题也具有强NP完全极小极大遗憾对应物。因此，具有性能保证的启发式算法可能具有很大的潜在价值，但只有少数这样的保证存在。组合优化问题的一个流行的启发式算法是计算原始问题的中点解。一个著名的结果是，中点解的遗憾最多是最优遗憾的2倍。除了一些学术上的例子表明这个界是紧的外，大多数例子都显示出更好的逼近比。使用这个下限，我们国家的算法，给出了一个实例依赖的性能保证中点的解决方案，最多为2。该算法的计算复杂度取决于考虑的最小最大遗憾问题，我们表明，我们的锐化保证可以计算在强多项式时间的几类组合优化问题。为了说明所提出的界的质量，我们使用它在一个分支和边界框架内的鲁棒最短路径问题。在一项实验研究中，这种方法与文献中的约束进行比较，我们发现在计算时间上有相当大的改进。
Minmax regret optimization aims at finding robust solutions that perform best in the worst-case, compared to the respective optimum objective value in each scenario. Even for simple uncertainty sets like boxes, most polynomially solvable optimization problems have strongly NP-complete minmax regret counterparts. Thus, heuristics with performance guarantees can potentially be of great value, but only few such guarantees exist.A popular heuristic for combinatorial optimization problems is to compute the midpoint solution of the original problem. It is a well-known result that the regret of the midpoint solution is at most 2 times the optimal regret. Besides some academic instances showing that this bound is tight, most instances reveal a way better approximation ratio.We introduce a new lower bound for the optimal value of the minmax regret problem. Using this lower bound we state an algorithm that gives an instance-dependent performance guarantee for the midpoint solution that is at most 2. The computational complexity of the algorithm depends on the minmax regret problem under consideration; we show that our sharpened guarantee can be computed in strongly polynomial time for several classes of combinatorial optimization problems.To illustrate the quality of the proposed bound, we use it within a branch and bound framework for the robust shortest path problem. In an experimental study comparing this approach with a bound from the literature, we find a considerable improvement in computation times.