On the Sphere Method of Linear Programming Using Multiple Interior Points Approach

Authors: Job H. Domingo, Carolina Bancayrin-Baguio

Abstract:

The Sphere Method is a flexible interior point algorithm for linear programming problems. This was developed mainly by Professor Katta G. Murty. It consists of two steps, the centering step and the descent step. The centering step is the most expensive part of the algorithm. In this centering step we proposed some improvements such as introducing two or more initial feasible solutions as we solve for the more favorable new solution by objective value while working with the rigorous updates of the feasible region along with some ideas integrated in the descent step. An illustration is given confirming the advantage of using the proposed procedure.

Keywords: Interior point, linear programming, sphere method, initial feasible solution, feasible region, centering and descent steps, optimal solution.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073691

References:

[1] Murty, Katta (2006). A New Practically Efficient Interior Point Method for LP Algorithmic Operations Research Vol.1 (2006) 3-19
[2] Murty, Katta (2009). New Sphere Methods for Linear Programs, Tutorials in Operations Research, INFORMS 2009.
[3] Murty, Katta (2008) Note on Implementing the New Sphere Method for LP Using Matrix Inversions Sparingly.
[4] Murty, Katta (2006) Linear equations, Inequalities, Linear Programs (LP), and a New Efficient Algorithm.