Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming

Abstract

Primal-slack ellipsoids are described which contain all of the optimal primal feasible solutions in a standard form variant of Karmarkar's projective algorithm for linear programming (LP). Using these ellipsoids, we show how to identify optimal basic variables using few additional arithmetic operations and also simultaneously reduce the size of the LP problem during the course of the algorithm. Some preliminary computational experiments are given which compare different stopping criteria.