Mauricio G.C. Resende and Geraldo Veiga
Extended version of published paper published in Network Flows and Matching: First DIMACS Implementation Challenge, D.S. Johnson and C.C. McGeoch, Eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 12, pp. 299-348, 1993
ABSTRACT
We describe DLNET, an
implementation of the dual affine scaling algorithm for minimum cost
capacitated network flow problems. The efficiency of this
implementation is the result of three factors: the small number of
iterations taken by interior point methods, efficient solution of the
linear system that determines the ascent direction using a
preconditioned conjugate gradient algorithm and strategies to produce an
optimal primal vertex solution. The combination of these
ingredients results in a code that can solve minimum cost network flow
problems having hundreds of thousands of vertices in a few hours of
running time on a workstation. We compare DLNET with network
simplex code NETFLO and relaxation code RELAXT-3 on an extensive range
of minimum cost network flow problems, including minimum cost
circulation, maximum flow and transshipment problems.
PostScript file
of full paper