An Implementation of the Dual Affine Scaling Algorithm for Minimum-Cost Flow on Bipartite Uncapacitated Networks
- 1 August 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 3 (3) , 516-537
- https://doi.org/10.1137/0803025
Abstract
. We describe an implementation of the dual affine scaling algorithm for linear programmingspecialized to solve minimum cost flow problems on bipartite uncapacitated networks.This implementation uses a preconditioned conjugate gradient algorithm to solve the system of linearequations that determines the search direction at each iteration of the interior point algorithm.Two preconditioners are considered: a diagonal preconditioner and a preconditioner based on theincidence matrix of an...Keywords
This publication has 16 references indexed in Scilit:
- Limiting behavior of the affine scaling continuous trajectories for linear programming problemsMathematical Programming, 1991
- The Auction Algorithm for Assignment and Other Network Flow Problems: A TutorialInterfaces, 1990
- An Empirical Evaluation of the KORBX® Algorithms for Military Airlift ApplicationsOperations Research, 1990
- Data Structures and Programming Techniques for the Implementation of Karmarkar's AlgorithmINFORMS Journal on Computing, 1989
- An implementation of Karmarkar's algorithm for linear programmingMathematical Programming, 1989
- Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow ProblemsOperations Research, 1988
- A new algorithm for the assignment problemMathematical Programming, 1981
- NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network ProblemsManagement Science, 1974
- Methods of conjugate gradients for solving linear systemsJournal of Research of the National Bureau of Standards, 1952
- Optimality and Degeneracy in Linear ProgrammingEconometrica, 1952