Design and Implementation of Large-Scale Primal Transshipment Algorithms
Bradley, Gordon H.
Brown, Gerald G.
Graves, Glen W.
MetadataShow full item record
A complete 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 transshipment problems solved is the most general of the minimum cost network flow models which include the capacitated and uncapacitated transportation problems and the classical assignment problem; these formulations are used for a large number of diverse applications to determine how (or at what rate) a good should flow through the arcs of a network to minimize total shipment costs. The presentation tailors the unified mathematical framework of linear programming to networks with special emphasis on data structures which are not only useful for basis representation, basis manipulation, and pricing mechanisms, but which also seem to be fundamental in general mathematical programming. A review of pertinent optimization literature accompanies computational testing of the most promising ideas. Tuning experiments for the network system, GNET, are reported along with important extensions such as exploitation of special problem structure, element generation techniques, postoptimality analysis, operation with problem generators and external problem files, and a simple noncycling pivot selection procedure which guarantees finiteness for the algorithm.
“Exceptional Paper” in Management Science, 24, 1, pp. 1-34, (1977 Lanchester Prize Finalist).
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Fu Chen-Hua (Monterey, California: Naval Postgraduate School, 1993-03);Efficient performance and high throughput are the major goals of the network performance management. How can we achieve these goal? First, it is necessary to know the network traffic situations. This thesis research ...
Naval Postgraduate School Center for Homeland Defense and Security (CHDS) (Monterey, California. Naval Postgraduate SchoolCenter for Homeland Defense and Security, 2006-07);July 2006. The July 2006 issue of Homeland Security Affairs offers articles about risk perception, domestic right wing extremist groups, social network analysis, and the impact of foreign policy on homeland security. It ...
Zhan, J.; Maltz, D.; Zhang, H.; Greenberg, A.; Hjalmtysson, G.; Rexford, J.; Xie, Geoffrey (2005-03);The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state ...