Multiple Centrality Corrections in a Primal--Dual Method
for Linear Programming
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.