A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

Abbas Seifi and Levent Tuncel

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.

The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a ``good'' starting point and a procedure for solving the augmented system arising from stochastic programming with recourse. We also present an application to large scale linear programming problems arising from planning under uncertainity.

Contact: ltuncel@watdragon.uwaterloo.ca

A. Seifi and L. Tun{\c c}el, A constant-potential infeasible-start interior-point algorithm with computational experiments and applications, {\it Research Report} 96--07, Department of Combinatorics and Optimization, University of Waterloo, Waterloo Ontario, Canada, June 1996.