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

Mauricio G.C. Resende's Home Page

Last modified: