Converting Linear Programs to Network Problems

We describe an algorithm which converts a linear program min{ cx | Ax = b, x 0} to a network flow problem, using elementary row operations and nonzero variable-scaling, or shows that such a conversion is impossible. If A is in standard form, the computational effort required is bounded by O ( rn ),...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 1980-08, Vol.5 (3), p.321-357
Main Authors: Bixby, Robert E, Cunningham, William H
Format: Article
Language:English
Subjects:
Algorithms
Conversion
Equivalence relation
Graphic matroids
Linear programming
Mathematical vectors
Matrices
Matrix
Matroids
network flows
Networks
Problems
Separators
Transshipment
Vertices
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe an algorithm which converts a linear program min{ cx | Ax = b, x 0} to a network flow problem, using elementary row operations and nonzero variable-scaling, or shows that such a conversion is impossible. If A is in standard form, the computational effort required is bounded by O ( rn ), where r is the number of rows and n is the number of nonzero entries of A . A method for determining whether a "binary matroid" is "graphic" plays an important role in the algorithm.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.5.3.321