Groupe d’études et de recherche en analyse des décisions

G-2021-05

The minimum mean cycle-canceling algorithm for linear programs

et

Cet article présente les propriétés de l'algorithme MMCC (minimum mean cycle-canceling) pour la résolution de programmes linéaires. Initialement conçu par Goldberg et Tarjan(1989) pour résoudre les problèmes de réseau pour lesquels il s'exécute en temps fortement polynomial, la plupart de ses propriétés sont préservées. Ceci au prix de l'adaptation du théorème de décomposition d'une solution ainsi de certaines définitions : celle d'un cycle et la manière de calculer son coût, le problème résiduel et le facteur d'amélioration en fin de phase. Nous utilisons également les conditions d'optimalité primales et duales énoncées sur le problème résiduel (Gauthier et al., 2014). Il s'avère que les solutions successives n'ont pas besoin d'être de base, qu'il n'y a pas de pivots dégénérés, et que les directions d'amélioration sont potentiellement intérieures en plus de celles suivant les arêtes. Pour résoudre un programme linéaire de dimension \( m \times n \), il faut \( O(n \Delta)\) phases, où \( \Delta \) dépend du nombre de contraintes \(m\) et de la matrice de coefficients. Puisque chaque phase comprend au plus \( n \) itérations que l'on peut résoudre en temps polynomial par un algorithme de points intérieurs, la complexité globale est pseudo-polynomiale.

, 14 pages