A Strongly Convergent Primal Algorithm for Generalized Networks.

摘要

A major computational problem that arises in the attempt to solve generalized network and network-related problems is degeneracy. In fact, using primal extreme point solution techniques, the number of degenerate pivots performed frequently ranges as high as 90% in large-scale applications. The purpose of this paper is to develop a special set of structural and logical relationships for generalized network problems that yields a new primal extreme point algorithm which avoids and/or exploits degeneracy. The major mathematical differences between this new algorithm and the simplex method are: (1) each basis examined is restricted to have a special topology, (2) the algorithm is finitely convergent without reliance upon external techniques such as lexicography or perturbation, and (3) a special screening criterion for nondegenerate basis exchanges is available that allows some of these exchanges to be recognized prior to finding the representation of an incoming arc. For these reasons, this algorithm has several computational advantages over the simplex-based codes recently developed for solving generalized network problems. (Author)