Technical Note—A Class of Linear Programs Convertible to Network Problems

William H. Cunningham
Additional contact information
William H. Cunningham: Universitat Bonn, Bonn, West Germany

Operations Research, 1983, vol. 31, issue 2, 387-391

Abstract: We consider a class of two-commodity network flow problems with additional, highly structured linear constraints in place of the usual capacity constraints. This class of linear programs arose as subproblems in a mixed integer programming formulation of a location model, and was solved by Ramakrishnan using a special purpose primal simplex algorithm. We show that, even though the constraint matrices of these problems are not transformable to constraint matrices of pure network problems, the problems themselves can be converted to pure network problems. The transformation depends on the existence of a set of variables whose non-negativity restrictions are redundant to the definition of the feasible region. We point out other situations in which such structure occurs.

Keywords: 481 minimum cost; 660 conversion to network problems (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.2.387 (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:31:y:1983:i:2:p:387-391

Access Statistics for this article

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