Conjugate Gradient Based Implementation of Interior Point Methods for Network Flow Problems

Sanjay Mehrotra and Jen-Shan Wang

This paper suggests enhancements to preconditiond conjugate gradient based implementation of interior point methods for linear network optimization problems. A new preconditioner is proposed and its effectiveness is demonstrated. We propose several additional refinements to the previous implementations, including an adaptive conjugate gradient termination criterion, and a new starting point solution. Our computational results are compared with results from PDNET, DLNET, CS3.3, RELAX-IV, and NETOPT (CPLEX3.0).

Technical Report 95-70, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, October, 1995.