Search

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. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to describe the development, implementation, and availability of a computer program for generating a variety of feasible network problems together with a set of benchmarked problems derived from it. The code "NETGEN" can generate capacitated and uncapacitated transportation and minimum cost flow network problems, and assignment problems. In addition to generating structurally different classes of network problems the code permits the user to vary structural characteristics within a class. Problems benchmarked on several codes currently available are provided in this paper since NETGEN will also allow other researchers to generate identical problems. In particular, the latter part of the paper contains the solution time and objective function value of 40 assignment, transportation, and network problems varying in size from 200 nodes to 8,000 nodes and from 1,300 arcs to 35,000 arcs. [ABSTRACT FROM AUTHOR]

The augmented predecessor indexing method is a procedure for efficiently updating the basis representation, flows, and node potentials in an adjacent extreme point (or `simplex' type) method for network problems, utilizing ideas due to ELLIS JOHNSON in his proposed application of a triple-label representation to networks. The procedure is extended here to accommodate the more complex basis structures and updating processes of the generalized network problem, specifying rules for expediting the calculations. [ABSTRACT FROM AUTHOR]