Converting Linear Programs to Network Problems
Robert E. Bixby, William H. Cunningham · Mathematics of Operations Research · 1980
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.
Cited by 119 works. doi:10.1287/moor.5.3.321
Authors
References
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithm 447: efficient algorithms for graph manipulation
- Lectures on matroids
- Efficient algorithms for graph manipulation
- Decomposition of regular matroids
- Design and Implementation of Large-Scale Primal Transshipment Algorithms
- Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
- Optimal Capacity Scheduling—II
- A network simplex method