Efficient implementation of the Goldberg–Tarjan minimum-cost flow algorithm

Abstract

Abstract The cost-scaling algorithm of Goldberg and Tarjan [Mathematics of Operations Research 15 (1990), 430-466] is known to be one of the most efficient algorithms for minimum–cost flow problems. However, its efficiency in practice depends on many implementation aspects. Moreover, the inclusion of several heuristics improves its performance drastically. This paper addresses important implementation aspects and describes the most efficient heuristics. Experimental results also highlight the effect of combining several heuristics. Keywords: Minimum-cost flowsGoldberg–Tarjan algorithmEfficient implementation