Ce constat a motivé tout d'abord l'étude de la complexité de cet algorithme sur des instances aléatoires (qui ne sont pas forcément très représentatives des usages réels), puis la smoothed complexity (Spielman & Shang-Hua).

On pourrait croire qu'il existe des études expérimentales à l'appui de ce constat : par exemple, rassembler des milliers de problèmes de programmation linéaire, notamment industriels (mais pas des instances spécifiquement conçues pour provoquer des comportements exponentiels), et compter sur chacun le nombre de pas avec les règles de pivot les plus courantes.

Or, je n'ai rien trouvé de tel.

Tout le monde sait bien...