An efficient implementation of a scaling minimum-cost flow algorithm

The scaling push-relabel method is an important theoretical development in the area of minimum-cost flow algorithms. We study practical implementations of this method. We are especially interested in heuristics which improve real-life performance of the method. Our implementation works very well over a wide range of problem classes. Some heuristics we develop may apply to other network algorithms. Our experimental work on the minimum-cost flow problem motivated theoretical work on related problems. (C) 1997 Academic Press.