An efficient implementation of a network interior point method

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

Go back

Mauricio G.C. Resende's Home Page

Last modified: 23 November 1995

Copyright Notice