A Very-Long-Step affine scaling for linear programming

Interior Point Methods combine computational simplicity with outstanding practical performance and efficiency for solving Linear Programs. In this paper, we study a safeguarded Very-Long-Step affine scaling framework that combines aggressive affine-scaling steps with an upper bound on the step parameter and periodic spacer iterations. Our proposed Very-Long-Step (VLS) algorithm relaxes the condition that constructed ellipsoids are necessarily interior to the feasible region. This relaxation results in longer, more advantageous steps. We provide proof of convergence, show numerical results on various test problems, and discuss the performance relative to other AFS implementations. We find that in each instance, the VLS algorithm requires fewer iterations than all the other tested variants.