RELAX-IV : a faster version of the RELAX code for solving minimum cost flow problems
RELAX-IV : a faster version of the RELAX code for solving minimum cost flow problems
复制标题
RELAX-IV：RELAX 代码的更快版本，用于解决最小成本流问题
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Decision Systems.
中科院分区：
文献类型：
--
作者：
D. Bertsekas;P. Tseng;Decision Systems.
双上升方法的结构特别适合于利用最小成本流动问题的良好初始对偶解。因此，这些方法对于再优化和灵敏度分析是非常有效的。在缺乏良好的初始对偶解的先验知识的情况下，可以尝试通过启发式初始化来找到这样的解。RELAX- iv是一种最小成本流代码，它将[BeT88a]、[BeT88b]的RELAX代码与基于最近提出的拍卖/顺序最短路径算法的初始化相结合。这种初始化被证明对加速解决困难问题非常有帮助，例如涉及长扩展路径，而松弛方法已经被认为是缓慢的。另一方面，对于已知速度非常快的问题类型，此初始化过程不会显著降低松弛方法的性能。
The structure of dual ascent methods is particularly well-suited for taking advantage of good initial dual solutions of minimum cost flow problems. For this reason, these methods are extremely efficient for reoptimization and sensitivity analysis. In the absence of prior knowledge of a good initial dual solution, one may attempt to find such a solution by means of a heuristic initialization. RELAX-IV is a minimum cost flow code that combines the RELAX code of [BeT88a], [BeT88b] with an initialization based on a recently proposed auction/sequential shortest path algorithm. This initialization is shown to be extremely helpful in speeding up the solution of difficult problems, involving for example long augmenting paths, for which the relaxation method has been known to be slow. On the other hand, this initialization procedure does not significantly deteriorate the performance of the relaxation method for the types of problems where it has been known to be very fast.