An Implementation of the Dual Affine Scaling Algorithm for Minimum-Cost Flow on Bipartite Uncapacitated Networks

Maurício G. C. Resende, Geraldo Veiga

SIAM Journal on Optimization · 1993 · 58 citations · 17 references

Concepts

Abstract

This paper describes an implementation of the dual affine scaling algorithm for linear programming specialized to solve minimum-cost flow problems on bipartite uncapacitated networks. This implementation uses a preconditioned conjugate gradient algorithm to solve the system of linear equations 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 the incidence matrix of an approximate maximum weighted spanning tree of the network. Under dual nondegeneracy this spanning tree allows for early identification of the optimal solution. By applying an $\epsilon $-perturbation to the cost vector, an optimal extreme-point primal solution is produced in the presence of dual degeneracy. The implementation is tested by solving several large instances of randomly generated assignment problems, comparing solution times with the network simplex code NETFLO and the relaxation algorithm code RELAX. This interior point algorithm greatly benefits from implementation in a parallel architecture. For the largest instances tested the interior point code was competitive with both the simplex and relaxation codes.

References

17