Efficient implementation of the Goldberg–Tarjan minimum-cost flow algorithm
Ursula Bünnagel, Bernhard Körte, Jens Vygen · Optimization methods & software · 1998
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.