Basic Dual Feasible Solutions for a Class of Generalized Networks

Fred Glover, D. Klingman and A. Napier
Additional contact information
Fred Glover: University of Colorado, Boulder, Colorado
D. Klingman: The University of Texas, Austin, Texas
A. Napier: Continental Oil Company, Ponca City, Oklahoma

Operations Research, 1972, vol. 20, issue 1, 126-136

Abstract: The generalized network problem and the closely related restricted dyadic problem occur frequently in applications of linear programming. Although they are next in order of computational complexity after pure network or distribution problems, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms comparable in speed to those for pure networks. In this paper we characterize the properties of a special class of generalized network problems that permit a dual feasible basic solution to be determined in one “pass” through the network. In particular, this class includes the class of pure network problems for which no such procedure has previously existed. Our algorithm also makes it possible to apply Lemke's dual method and the poly-ω technique of Charnes and Cooper in an efficient manner to solve capacitated (pure) network problems.

Date: 1972
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.20.1.126 (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:oropre:v:20:y:1972:i:1:p:126-136

Access Statistics for this article

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