G-2021-05
The minimum mean cycle-canceling algorithm for linear programs
et référence BibTeX
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.
Paru en février 2021 , 14 pages