Solving Generalized Networks

Gerald G. Brown and Richard D. McBride
Additional contact information
Gerald G. Brown: Naval Postgraduate School, Monterey, California 93943
Richard D. McBride: School of Business Administration, University of Southern California, Los Angeles, California 90089-4121

Management Science, 1984, vol. 30, issue 12, 1497-1523

Abstract: A complete, unified description is given of the design, implementation and use of a family of very fast and efficient large-scale minimum-cost (primal simplex) network programs. The class of capacitated generalized transshipment problems solved includes the capacitated and uncapacitated generalized transportation problems and the continuous generalized assignment problem, as well as the pure network flow models which are specializations of these problems. These formulations are used for a large number of diverse applications to determine how (or at what rate) flows through the arcs of a network can minimize total shipment costs. A generalized network problem can also be viewed as a linear program with at most two nonzero entries in each column of the constraint matrix; this property is exploited in the mathematical presentation with special emphasis on data structures for basis representation, basis manipulation, and pricing mechanisms. A literature review accompanies computational testing of promising ideas, and extensive experimentation is reported which has produced GENNET, an extremely efficient family of generalized network systems.

Keywords: networks/graphs: flow algorithms; networks/graphs: generalized (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.30.12.1497 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:30:y:1984:i:12:p:1497-1523

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().