Identifying the Optimal Face of a Network Linear Program with a Globally Convergent Interior Point Method

Mauricio G.C. Resende, Takashi Tsuchiya, and Geraldo Veiga

In Large Scale Optimization: State of the Art, W.W. Hager, D.W. Hearn and P.M. Pardalos, Eds., Kluwer, pp. 362-387, 1994


Based on recent convergence results for the affine scaling algorithm for linear programming, we investigate strategies to identify the optimal face of a minimum cost network flow problem.  In the computational experiments described, one of the proposed optimality indicators is used to implement an early stopping criterion in DLNET an implementation of the dual affine scaling algorithm for solving minimum cost network flow problems.  We conclude from the experiments that the new indicator is far more robust than the one used in earlier versions of DLNET.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 28 June 2002

Copyright Notice