Generalized Networks: A Fundamental Computer-Based Planning Tool

Abstract

This paper documents the recent emergence of generalized networks as a fundamental computer-based planning tool and demonstrates the power of the associated modeling and solution techniques when used together to solve real-world problems. The first sections of the paper give a non-technical account, of how generalized networks are used to model a diversity of significant practical problems. To begin, we discuss the model structure of a generalized network (GN) and provide a brief survey of applications which have been modeled as GN problems. Next we explain a somewhat newer modeling technique in which generalized networks form a major, but not the only, component of the model. The later sections give a technical exposition of the design and analysis of computer solution techniques for large-scale GN problems. They contain a study of GN solution strategies within the framework of specializations of the primal simplex method. We identify an efficient solution procedure derived from an integrated system of start, pivot, and degeneracy rules. The resulting computer code is shown, on large problems, to be at least 50 times more efficient than the LP system, APEX III.