Résumés
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.
Keywords:
- Linear programming (LP),
- Dantzig’s simplex method,
- boundary methods,
- gravitational method,
- interior point method,
- avoiding zigzagging,
- solving LPs without matrix inversions,
- strongly polynomial algorithm for LP
Veuillez télécharger l’article en PDF pour le lire.
Télécharger