Experimental Evaluation of the Push-Relabel Method for the Minimum-Cost FlowProblem (Extended Abstract)

摘要

The generalized cost-scaling method is theoretically superior to other methodsfor solving the minimum-cost flow problem, in the sense that it leads to the best running time bounds currently known under the assumption that the absolute values of costs are not too big. There is some evidence that the method should perform well in practice as well: an earlier cost-scaling algorithm of Blend and Jensen was shown to be competitive with a well-established network simplex code. The method is very flexible and has many variants. Which version of the method works best in practice. But how good is the method in practice. These are the questions addressed in our study. Generalized cost scaling framework can accommodate several very different algorithms, such as the push-relabel method, the blocking flow method, multiple scaling algorithms, and cycle-canceling algorithms. We restrict our study only to push-relabel variant of the cost-scaling approach. This variant is the most promising since, in the context of the closely related maximum flow problem, several researchers reported its superior performance compared to other popular techniques. For this reason we believe that the experimental study of the push-relabel variants of the method should be done first, and in this study restrict ourself to these variants.