On the facet pivot simplex method for linear programming

Ce papier propose une nouvelle méthode du simplexe à pivot de facette pour la programmation linéaire qui démontre une supériorité prometteuse par rapport à l'approche traditionnelle à pivot de sommet lors des tests numériques, offrant un nouvel espoir pour la découverte d'un algorithme de pivot en temps polynomial.

L'essentiel

Imaginez que vous essayez de trouver l'endroit absolument idéal pour installer un stand de limonade dans une ville. La ville a la forme d'un bâtiment complexe à multiples faces (un polytope), et vous voulez trouver le coin qui vous rapportera le plus d'argent.

Depuis plus de 70 ans, la méthode standard pour y parvenir est la Méthode de Pivot de Sommet (inventée par George Dantzig). Imaginez cette méthode comme un touriste se promenant à l'extérieur du bâtiment. Il commence à un coin (sommet), examine les coins voisins, et marche vers celui qui semble meilleur. Il continue de sauter de coin en coin le long des arêtes jusqu'à trouver le meilleur endroit.

Le problème est que parfois, le bâtiment est conçu avec un labyrinthe astucieux de coins. Dans les scénarios du pire cas, le touriste pourrait devoir passer par chaque coin unique dans un ordre spécifique et épuisant avant de trouver le meilleur. C'est comme traverser un labyrinthe qui devient exponentiellement plus long à mesure que le bâtiment grandit.

La Nouvelle Idée : La Méthode de « Pivot de Facette »

Dans cet article, l'auteur, Yaguang Yang, propose une nouvelle façon de résoudre ce problème appelée la Méthode Simplexe de Pivot de Facette.

Au lieu de marcher le long des coins (sommets), imaginez que vous êtes un inspecteur de construction examinant les facettes du bâtiment.

• L'Ancienne Façon (Sommet) : Vous êtes un touriste sautant de coin en coin.
• La Nouvelle Façon (Facette) : Vous êtes un inspecteur échangeant les facettes qui définissent votre « base » actuelle pour vous rapprocher du meilleur endroit.

Voici comment fonctionne la nouvelle méthode en termes simples :

1. Commencez par les Facettes, pas les Coins : Au lieu de commencer à un coin, l'algorithme commence par choisir un ensemble de facettes (contraintes) qui définissent une position temporaire, peut-être imparfaite.
2. Échangez des Facettes, pas des Coins : L'algorithme examine les facettes qui sont actuellement « brisées » ou non satisfaites (comme une facette qui penche dans la mauvaise direction). Il choisit le pire et l'échange contre une facette différente qui aide à résoudre le problème.
3. Pas de Détour « Phase 1 » : L'ancienne méthode nécessite souvent un long et coûteux voyage de « Phase 1 » juste pour trouver un coin de départ valide avant même de pouvoir commencer à chercher le meilleur. La nouvelle méthode est astucieuse : elle commence par une configuration mathématiquement garantie de fonctionner immédiatement, sautant ainsi entièrement ce long détour. C'est comme avoir une clé magique qui ouvre la porte du bâtiment instantanément, plutôt que d'essayer de crocheter la serrure d'abord.

Pourquoi est-ce excitant ?

L'article affirme que cette nouvelle méthode est très prometteuse pour deux raisons principales :

• Elle est plus rapide sur les labyrinthes difficiles : L'auteur l'a testée sur des « cubes de Klee-Minty », qui sont des labyrinthes mathématiques spécifiquement conçus pour piéger l'ancienne méthode du touriste en la forçant à prendre une éternité. La nouvelle méthode d'échange de facettes a résolu ces labyrinthes beaucoup plus rapidement, ne prenant que quelques étapes au lieu de milliers.
• Elle est plus robuste : Lors des tests sur une vaste collection de problèmes mathématiques réels (les benchmarks Netlib), la nouvelle méthode a résolu avec succès presque tous d'entre eux. L'ancienne méthode du « touriste » s'est parfois retrouvée bloquée ou a pris très longtemps, et la méthode « duale » (un autre type de touriste) a parfois abandonné parce que la géométrie du bâtiment était trop astucieuse. La méthode d'échange de facettes a mieux géré ces géométries complexes.

Le Bémol (et l'Espoir)

L'article admet que pour des problèmes très grands et simples, l'ancienne méthode (ou d'autres méthodes comme les méthodes « Point Intérieur », qui sont comme faire voler un drone au milieu du bâtiment) pourrait encore être plus rapide.

Cependant, le grand espoir est que cette nouvelle approche d'« échange de facettes » pourrait être la clé pour résoudre un mystère mathématique célèbre vieux de 60 ans : Peut-on trouver une méthode garantie d'être rapide (temps polynomial) pour chaque problème ?

Pendant des décennies, les mathématiciens ont tenté de prouver que l'ancienne méthode de « saut de coin » était assez rapide, mais ils ont trouvé des cas où elle est incroyablement lente. Cette nouvelle méthode d'« échange de facettes » offre une perspective fraîche. Elle ne repose pas sur les mêmes vieilles règles, et les premiers tests suggèrent qu'elle pourrait être le chemin vers une solution à la fois rapide et fiable pour tous les types de problèmes de programmation linéaire.

En résumé : L'article présente une nouvelle façon de résoudre des problèmes d'optimisation mathématique en échangeant des « facettes » au lieu de sauter des « coins ». Elle saute les étapes d'installation ennuyeuses, gère mieux les labyrinthes complexes que les anciennes méthodes, et redonne aux mathématiciens un nouvel espoir de trouver une solution parfaite et rapide pour tous les problèmes.

Résumé technique

Résumé technique : Sur la méthode du simplexe à pivot de facette pour la programmation linéaire

Énoncé du problème
L'article traite de l'efficacité computationnelle et des limitations théoriques de la méthode standard du simplexe à pivot de sommet pour résoudre les problèmes de programmation linéaire (PL). Bien que la méthode du simplexe de Dantzig à pivot de sommet reste hautement efficace en pratique, elle ne dispose pas d'une borne de complexité prouvée en temps polynomial. Théoriquement, le scénario du pire cas pour les méthodes à pivot de sommet implique un nombre exponentiel d'itérations (comme démontré par les cubes de Klee-Minty), et la recherche d'un algorithme de pivot polynomial est restée insaisissable pendant des décennies. De plus, les méthodes à pivot de sommet traditionnelles nécessitent souvent un processus « Phase I » coûteux en calcul pour trouver une solution de base initiale réalisable, en particulier pour les problèmes de PL généraux impliquant des contraintes d'inégalité et des bornes.

Méthodologie
Les auteurs proposent une méthode du simplexe à pivot de facette qui déplace fondamentalement l'opération de pivot des sommets vers les facettes (contraintes).

• Formulation générale : La méthode opère sur une formulation générale de PL :
  $$\min c^T x$$
  $$\text{sous contraintes } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  Contrairement aux formes standards qui convertissent les inégalités en égalités via des variables d'écart, cette approche traite les contraintes d'inégalité directement comme des facettes du polytope réalisable.

• Logique algorithmique :

  • Définition de la base : Au lieu d'une base de variables (sommets), l'algorithme maintient une base de $d$ facettes linéairement indépendantes (contraintes), où $d$ est la dimension du problème.
  • Processus itératif : L'algorithme démarre avec une solution de base initiale (souvent dérivée directement des contraintes de bornes) qui n'est pas nécessairement réalisable. À chaque itération, il sélectionne une facette entrante (une contrainte non de base) et une facette sortante (une contrainte de base) pour mettre à jour la base.
  • Faisabilité et optimalité : L'algorithme maintient une représentation du vecteur objectif $c$ comme une combinaison linéaire à coefficients non négatifs des facettes de base actuelles (satisfaisant une condition dérivée du lemme de Farkas). Il améliore itérativement la solution en remplaçant des facettes pour réduire les violations de contraintes.
  • Arrêt : Le processus s'arrête lorsqu'une solution de base réalisable est trouvée. Selon les théorèmes d'optimalité présentés, si le vecteur objectif peut être exprimé comme une combinaison à coefficients non négatifs des facettes de base actives en un point réalisable, ce point est optimal.
  • Convergence finie : L'article prouve que si la « règle du plus petit/plus bas indice » est appliquée pour sélectionner les facettes entrantes et sortantes, l'algorithme évite les cycles et se termine en un nombre fini d'étapes.

• Distinctions clés par rapport au simplexe dual : Bien que la méthode à pivot de facette partage certaines similarités géométriques avec la méthode du simplexe dual (déplacement entre des bases de contraintes), elle se distingue par le fait qu'elle opère exclusivement sur le problème primal sans construire ni résoudre explicitement un problème dual. Elle gère la forme générale directement, évitant la conversion vers la forme standard.

Contributions clés

1. Proposition algorithmique : L'article introduit un algorithme spécifique de pivot de facette (Algorithme 4.1) qui résout des problèmes de PL généraux sans nécessiter d'étape d'initialisation de Phase I.
2. Garanties théoriques : Les auteurs fournissent des preuves mathématiques (fondées sur le lemme de Farkas) démontrant que l'algorithme trouve une solution optimale en un nombre fini d'itérations et identifie correctement les problèmes non réalisables ou non bornés.
3. Implémentation : Une implémentation MATLAB de l'algorithme est fournie, ainsi que des implémentations du simplexe de Dantzig, du simplexe dual et des méthodes de points intérieurs pour comparaison.
4. Gestion des contraintes : La méthode gère naturellement les bornes inférieures et supérieures ainsi que les variables libres sans introduire de variables d'écart artificielles, résultant en une taille de problème réduite par rapport aux conversions en forme standard.

Résultats expérimentaux
Les auteurs ont mené des tests numériques sur plusieurs ensembles de référence :

• Benchmarks Netlib : Sur les problèmes Netlib standards avec bornes inférieures et supérieures, la méthode à pivot de facette a généralement nécessité moins de secondes CPU que la règle du pivot le plus négatif de Dantzig. Elle a résolu avec succès des problèmes où la méthode du simplexe dual échouait en raison d'une déficience de rang ou d'un mauvais conditionnement.
• Problèmes à grande échelle : Pour des problèmes très grands (par exemple, $n > 50\,000$), les méthodes de points intérieurs (IPM) ont surpassé toutes les méthodes de pivot, comme prévu. Cependant, la méthode à pivot de facette a montré une robustesse là où la méthode du simplexe dual échouait.
• Cubes de Klee-Minty : La méthode à pivot de facette a démontré des performances nettement supérieures à la méthode à pivot de sommet de Dantzig sur les variantes de Klee-Minty, nécessitant beaucoup moins d'itérations (souvent linéaires ou quasi-linéaires en fonction de la dimension $d$) par rapport aux itérations exponentielles requises par la méthode à pivot de sommet.
• Problèmes généraux aléatoires : Pour les problèmes de PL généraux nécessitant une Phase I dans les méthodes standards, la méthode à pivot de facette a été significativement plus efficace que la méthode de Dantzig car elle contournait l'initialisation de Phase I.
• Problèmes aléatoires standards : Pour les problèmes de PL standards où une Phase I n'est pas requise, la méthode de Dantzig s'est révélée légèrement plus efficace en temps CPU, bien que les nombres d'itérations soient comparables.

Signification et affirmations
L'article affirme que la méthode du simplexe à pivot de facette offre une alternative prometteuse aux méthodes basées sur les sommets, en particulier pour les problèmes de PL généraux avec contraintes d'inégalité. Sa signification principale réside dans :

• L'élimination de la Phase I : En démarrant à partir d'une solution de base dérivée des contraintes de bornes, elle évite la phase d'initialisation coûteuse requise par les méthodes du simplexe traditionnelles pour les problèmes généraux.
• Robustesse : Elle démontre une stabilité numérique supérieure à la méthode du simplexe dual sur les problèmes Netlib mal conditionnés.
• Espoir de complexité polynomiale : Bien que les auteurs n'affirment pas avoir prouvé une borne de temps polynomial, ils suggèrent que ce nouveau type d'algorithme de pivot (opérant sur les facettes plutôt que sur les sommets) offre une nouvelle voie de recherche pour trouver une méthode du simplexe à pivot polynomial, répondant au 9e problème de Smale.
• Efficacité pratique : La méthode s'avère hautement compétitive et souvent supérieure à la méthode de Dantzig pour les problèmes impliquant de nombreuses contraintes d'inégalité, sans la surcharge de les convertir en égalités.

Les auteurs maintiennent un ton modeste, reconnaissant que les méthodes de points intérieurs restent supérieures pour les problèmes à très grande échelle et que la méthode à pivot de facette est une nouvelle direction nécessitant des investigations supplémentaires pour comprendre pleinement ses bornes de complexité théorique.