Complexity and Approximation in Reoptimization
Complexity and Approximation in Reoptimization
复制标题
重新优化的复杂性和近似
DOI：
10.1142/9781848162778_0004
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
G. Ausiello
中科院分区：
文献类型：
--
作者：
B. Escoffier;V. Bonifaci;G. Ausiello
在本调查中，考虑了以下模型。我们假设计算困难的优化问题的实例I已经被解决，并且我们知道这样的实例的最优解。然后提出一个新的实例I′，它是通过对实例I作微小的扰动而得到的。我们如何利用我们对实例I的解的知识，以有效的方式计算实例I′的（近似）解？这种计算模型被称为再优化，在各种情况下都有实际意义。在这篇文章中，我们首先讨论了什么样的性能，我们可以预期的特定类别的问题，然后我们提出了一些经典的优化问题（即最大背包，最小施泰纳树，调度），这种方法已经卓有成效地应用。随后，我们解决车辆路径问题，我们展示了如何重新优化的方法可以用来获得良好的近似解决方案，在一个有效的方式为这些问题。
In this survey the following model is considered. We assume that an instance I of a computationally hard optimization problem has been solved and that we know the optimum solution of such instance. Then a new instance I′ is proposed, obtained by means of a slight pertur- bation of instance I. How can we exploit the knowledge we have on the solution of instance I to compute a (approximate) solution of instance I′ in an efficient way? This computation model is called reoptimization and is of practical interest in various circumstances. In this article we first discuss what kind of performance we can expect for specific classes of problems and then we present some classical optimization problems (i.e. Max Knapsack, Min Steiner Tree, Scheduling) in which this approach has been fruitfully applied. Subsequently, we address vehicle routing prob- lems and we show how the reoptimization approach can be used to obtain good approximate solution in an efficient way for some of these problems.