Solving embedded generalized network problems (Q1058978)

A complete, unified description is given of the design and implementation of a fast and efficient program which solves linear programming problems with network substructures. The very efficient generalized network procedures which have recently been developed are extended in this paper to produce an algorithm, called EMNET, which can solve generalized network problems with additional constraints and additional (complicating) variables. The only requirement on the network substructure is that it contain, at most two nonzero entries in each column. This requirement is the most general possible for network substructures. Many large linear programming problems can be placed in this form by a simple rearrangement of its rows and columns. Preliminary computational experience indicates EMNET is about five times faster than MINOS. The algorithm presented should provide a very efficient and fast solution for many linear programming problems involving production scheduling, distribution, facility location and personnel assignment. These problems tend to contain large embedded network substructures.