Sphere Methods for LP
Keywords:Linear Programming (LP), Interior point methods (IPMs), Large scale LPs, Ball centers of polytopes, Solving LPs using matrix inversions sparingly.
AbstractThe sphere method for solving linear programs operates with only a subset of constraints in the model in each iteration, and thus has the advantage of handling instances which may not be very sparse. In this paper we discuss enhancements, and improved versions Sphere Methods 2, 2.1 which improve performance by 20 to 80%. Additional steps that can improve performance even more are also presented.
How to Cite
Murty, K. G., & Oskoorouchi, M. R. (2010). Sphere Methods for LP. Algorithmic Operations Research, 5(1), Pages 21 – 33. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/11168