A New Practically Efficient Interior Point Method for LP

Authors

  • Katta G Murty

Abstract

In this paper we briefly review the importance of LP (linear programming), and Dantzig’s main contributions to OR (Operations Research), mathematics, and computer science. In [11, 3] gravitational methods for LP have been introduced. Several versions exist. The three main versions discussed there use a ball of (a): 0 radius, (b): small positive radius, and (c): the ball of largest possible radius with the given center that will completely fit within the polytope, with the option of changing its radius as the algorithm progresses. In versions (a) and (b), after the first move, the center of the ball always remains very close to the boundary (because the ball hugs the boundary), and hence these versions behave like other boundary algorithms such as the simplex algorithm in terms of exponential complexity in the worst case [9]. Here we discuss a gravitational method of type (c) that behaves like an interior point method [8,20, 21]. To guarantee that the ball has the largest possible radius, it uses a new centering strategy that moves any interior feasible solution x0 to the center of the intersection of the feasible region with the objective hyperplane through x0, before beginning the gravitational descent moves. We show that this strategy leads to a strongly polynomial algorithm for LP in terms of the number of centering steps. Also, using this centering strategy, we discuss a method that solves LPs efficiently using no matrix inversions.

Downloads

Published

2006-01-24

How to Cite

Murty, K. G. (2006). A New Practically Efficient Interior Point Method for LP. Algorithmic Operations Research, 1(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/93

Issue

Vol. 1 No. 1 (2006)

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.