Multiple Centrality Corrections in a Primal--Dual Method for Linear Programming

Jacek Gondzio

A modification of (infeasible) primal--dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem it is determined right after preprocessing KKT system and prior to optimization process. The harder the factorization, the more advantageous higher order corrections might prove.

Computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real--life LP models arising from applications. The use of multiple centrality corrections gives in the average 25% to 40% reduction in the number of iterations compared with widely used second order predictor--corrector method. This translates into 20% to 30% savings in CPU time.

Technical Report 1994.20, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, Bd. Carl-Vogt 102, 1211 Geneva, Switzerland, November 1994, revised May 1995.

[DVI] [POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]