A Note on Specialized Versus Unspecialized Methods for Maximum Flow Problems

摘要

A study developing highly efficient versions of both primal simplex and labeling methods for maximum flow problems has disclosed the surprising superiority of specialized primal methods. These provocative findings not only overturn standard expectation about the relative performance of simplex versus labeling approaches, but also raise the intriguing question of whether--or to what extent--it is useful to develop specialized methods for maximum flow problems. This issue was investigated by testing both specialized and unspecialized primal simplex codes on the same maximum flow problems using the same computer and compiler. Considering the possibility that some general primal network codes may be better tuned to maximum flow applications than others, a code was obtained which was timed for maximum flow problems in terms of using a special tree orientation, pricing subroutine, and pivot selection subroutine. The specialized primal code used in the tests is the SEQCS code. Hereafter it is, respectively, refer to these codes as GENERAL and SPECIAL. The tests of the two methods were conducted on four types of network structures: random (R), multi-terminal random (MR), transit grid (TG), and hard (H). It is found after testing 185 maximum flow problems embodying these diverse structures that the SPECIAL code is substantially more efficient than GENERAL, in spite of th fact that GENERAL was demonstrated superior to the specialized maximum flow procedures it was previously tested against. The R problems were generated by randomly selecting ordered node pairs to identify the arcs (avoiding duplication), and these were in turn randomly assigned capacities from a predefined interval.