Computational Comparison of the Primal Simplex and Relaxation Algorithms for Solving Minimum Cost Flow Networks

摘要

This thesis examines the relative computational efficiencies of two advanced network minimum cost flow problem solution methodologies: the primal simplex specialization to networks developed by Bradley, Brown and Graves (1977)--GNET and XNET, and a Lagrangian relaxation method developed by Bertsekas and Tseng (1988)--RELAX-II and RELAX-II. Additionally, the relaxation method description is clarified and potential implementation improvements are investigated. Research by Bertsekas and Tseng has shown the relaxation codes to be on the order of four to five times faster than the primal simplex codes. This thesis fails to duplicate those results. While the relaxation codes do perform faster in many circumstances when solving purely random problems, the primal simplex codes are still closely competitive. In particular, the primal simplex codes appear more efficient at solving capacitated transshipment problems in networks with an echelon structure, and in networks with many more sinks than sources. Primal simplex codes also require about half the computer storage of the relaxation codes. The research has produced compelling evidence that the relaxation algorithms can be further refined. All indications appear to reinforce the desirability of prioritizing by absolute deficit the node selection process used in both relaxation codes. Further research is recommended. Keywords: Mathematical computations; Military theses; Computing; Computer processing. (kt)