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