AN EFFICIENT IMPLEMENTATION OF A SCALING MINIMUM-COST FLOW ALGORITHM

The scaling push-relabel method is an important theoretical developmen t in the area of minimum-cost flow algorithms. We study practical impl ementations 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 wo rk on the minimum-cost flow problem motivated theoretical work on rela ted problems. (C) 1997 Academic Press.