An implementation of the dual affine scaling algorithm for minimum cost flow on bipartite uncapacitated networks

Mauricio G.C. Resende and Geraldo Veiga

SIAM Journal on Optimization, vol. 3, pp. 516-537, 1993

ABSTRACT

We describe 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.  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 if implemented in a parallel architecture.  For the largest instances tested, the interior point code was competitive with both the simplex and relaxation codes.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 23 November 1995

Copyright Notice