Convergence results and numerical experiments on a linear programming hybrid algorithm (Q1095026)

A modification of Karmarkar's algorithm for linear programming successively generates column-scaled equivalents of the original linear program, and in the scaled coordinates obtains improvements according to steepest descent directions. As an interior-feasible-preserving algorithm, termination requires a purification algorithm to obtain a dual basic optimal solution. Together the two algorithms comprise a `hybrid' procedure for solving linear programs. In this paper we present some convergence results on the Phase II and Phase I portions of the scaling algorithm. We also present results of numerical experiments on examples of Klee-Minty type which show sensitivity to the starting interior-feasible point and steepest descent step size.