Sphere Methods for LP

Authors

  • Katta G. Murty University of Michigan
  • Mohammad R. Oskoorouchi California State University San Marcos

Keywords:

Linear Programming (LP), Interior point methods (IPMs), Large scale LPs, Ball centers of polytopes, Solving LPs using matrix inversions sparingly.

Abstract

The 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.

Author Biographies

Katta G. Murty, University of Michigan

Professor, Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, MI-48109-2117, USA.

Mohammad R. Oskoorouchi, California State University San Marcos

Department of Information Systems and Operations Management, College of Business Administration, California State University San Marcos, San Marcos, CA 92096-0001, USA,

Downloads

Published

2010-04-14

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

Issue

Vol. 5 No. 1 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.