Des chercheurs découvrent une méthode pour accélérer la programmation linéaire en nombres entiers

Des chercheurs se rapprochent d’une nouvelle limite de vitesse pour la programmation linéaire en nombres entiers

• La programmation linéaire en nombres entiers (ILP) aide à trouver des solutions à divers problèmes du monde réel.
• Des chercheurs ont découvert une nouvelle méthode permettant d’exécuter l’ILP beaucoup plus rapidement.

Présentation du problème du voyageur de commerce

• Le problème du voyageur de commerce est l’un des plus anciens problèmes de calcul connus : il consiste à trouver l’itinéraire idéal passant par une liste donnée de villes en minimisant le kilométrage total.
• Bien qu’il paraisse simple, ce problème est notoirement difficile, et une stratégie de force brute consistant à vérifier tous les itinéraires possibles devient impraticable dès que le nombre de villes dépasse une poignée.
• À la place, on applique un modèle mathématique rigoureux appelé programmation linéaire pour approximer grossièrement le problème sous forme d’un ensemble d’équations, puis examiner systématiquement les combinaisons possibles afin de trouver la meilleure solution.

Importance de la programmation linéaire en nombres entiers

• Il est parfois nécessaire d’optimiser un problème avec des nombres entiers.
• La programmation linéaire en nombres entiers (ILP) est populaire dans les applications impliquant des décisions discrètes, notamment la planification de la production, la planification des équipages aériens et le routage de véhicules.
• L’ILP est au cœur de la recherche opérationnelle, tant en théorie qu’en pratique, selon Santosh Vempala, informaticien au Georgia Institute of Technology.

Progrès des algorithmes d’ILP

• Pendant plus de 60 ans après la première formalisation de l’ILP, les chercheurs ont découvert divers algorithmes pour résoudre les problèmes d’ILP, mais tous nécessitaient un nombre d’étapes relativement élevé.
• Des travaux récents de Victor Reis et Thomas Rothvoss ont permis le plus grand bond en avant en temps d’exécution depuis des décennies.
• Ils ont combiné des outils géométriques pour restreindre les solutions possibles et ont conçu un nouvel algorithme plus rapide qui résout l’ILP en un temps presque identique à celui du cas binaire.

Comment résoudre un problème d’ILP

• L’ILP consiste à transformer un problème donné en une série d’équations linéaires, avec la contrainte que ces équations doivent satisfaire certaines inégalités.
• Ces équations reposent sur les détails du problème d’origine, mais la structure fondamentale d’un problème d’ILP reste la même, ce qui offre aux chercheurs une méthode unique pour s’attaquer à des problèmes très variés.

Compréhension théorique des algorithmes d’ILP

• Le nouvel algorithme n’a pas encore été utilisé pour résoudre des problèmes logistiques réels, mais cela souligne l’importance de la compréhension des problèmes théoriques.
• Les chercheurs gardent l’espoir d’améliorer encore l’efficacité de calcul de l’ILP, mais cela nécessitera des idées fondamentalement nouvelles.

Avis de GN⁺

• Cette recherche représente une avancée importante à l’intersection de l’informatique et des mathématiques. Elle présente notamment un fort potentiel pour améliorer considérablement l’efficacité de l’ILP utilisée pour résoudre des problèmes logistiques complexes.
• Le nouvel algorithme demandera encore beaucoup de travail avant de pouvoir être appliqué à des applications réelles, mais les progrès de la compréhension théorique peuvent contribuer de manière importante aux futures améliorations algorithmiques et au développement des technologies associées.
• Cet article apporte une information intéressante aux chercheurs en informatique et aux personnes intéressées par la résolution de problèmes mathématiques, tout en soulignant l’importance de nouvelles approches pour résoudre des problèmes complexes.

[GN⁺]

Commentaires sur Hacker News

• Réduire la borne algorithmique supérieure des problèmes NP-complets est très intéressant, mais cela n’a pas forcément de lien direct avec l’amélioration du temps d’exécution pour résoudre des problèmes réels.

  • Les solveurs de programmation mixte en nombres entiers (MIP) utilisent divers algorithmes et heuristiques.
  • La constitution d’une bibliothèque d’heuristiques et de stratégies explique pourquoi les améliorations des solveurs MIP dépassent la loi de Moore.
  • De 1990 à 2014, les améliorations du matériel ont été de 6 500×, mais le logiciel a contribué à un gain de performance de 870 000×.
  • L’article cité pourrait être une pièce supplémentaire du puzzle dans l’amélioration continue des performances des solveurs MIP, mais rien n’est certain.

• Le nouvel algorithme n’a pas encore été utilisé pour résoudre de vrais problèmes logistiques.

  • Parce qu’il faudrait trop de travail pour mettre à jour les programmes actuels.
  • Mais selon Rothvoss, il s’agit d’une compréhension théorique d’un problème ayant des applications fondamentales.

• Le titre « Integer Linear Programming » devrait le préciser, car la partie entière est de loin la plus importante.

  • Des algorithmes en temps polynomial pour la programmation linéaire sont connus depuis des décennies, mais la programmation linéaire en nombres entiers est NP-difficile.

• Les ingénieurs logiciels devraient apprendre la programmation linéaire.

  • De nombreux problèmes peuvent être formulés comme des optimisations linéaires.
  • Par exemple, un problème portant sur le nombre moyen minimal d’échanges nécessaires pour placer des boules de billard dans la bonne position de départ sur un triangle peut être résolu à l’aide de la programmation linéaire.

• Cet article n’examine pas directement les groupes d’espace, mais il serait intéressant de voir s’il peut servir à généraliser la simplification de l’« espace » du problème.

  • L’auteur n’est pas mathématicien mais architecte, et en tant que personne qui étudie les trajets à travers des structures en nid d’abeilles générées, il estime que ce résultat mérite d’être approfondi.

• La citation tirée du livre de Sapolsky sur le problème du voyageur de commerce, « Determined: A Science of Life without Free Will », n’est peut-être pas pertinente pour les développeurs logiciels, mais elle reste fascinante.

  • Les fourmis vérifient huit emplacements à la recherche de nourriture, ce qui constitue une version du célèbre « problème du voyageur de commerce ».
  • Les informaticiens peuvent utiliser des « fourmis virtuelles » pour résoudre ce type de problèmes, ce qu’on appelle désormais l’intelligence en essaim.

• L’auteur a étudié la recherche opérationnelle à Stanford en 1985/86 et a suivi le cours de George Dantzig, mais il est devenu ingénieur logiciel plutôt que spécialiste de la recherche opérationnelle.

  • Il trouve intéressant de voir tout ce qui a été appris sur les algorithmes de programmation linéaire.

• De nombreux problèmes d’optimisation discrète peuvent être transformés en programmes linéaires.

  • C’est un ensemble d’outils extrêmement puissant, au même titre que les solveurs SAT.

• En complexité théorique, les méthodes de points intérieurs peuvent être meilleures que le simplexe pour les LP, mais dans la pratique, un simplexe bien réglé l’emporte presque toujours.