Des chercheurs découvrent comment accélérer la programmation linéaire en nombres entiers
(quantamagazine.org)- Pour les problèmes d’optimisation qui exigent des décisions en nombres entiers, comme la planification de la production, l’affectation des équipages ou le routage de véhicules, Victor Reis et Thomas Rothvoss proposent un nouvel algorithme qui réduit fortement le temps d’exécution de l’ILP
- Comme l’ILP est plus difficile que la programmation linéaire classique et qu’il n’y avait presque pas eu d’amélioration record depuis les années 1980, ce résultat est considéré comme une avancée majeure après plusieurs décennies
- La nouvelle approche combine des outils géométriques traitant l’intersection entre réseaux et corps convexes afin de resserrer plus fortement l’espace des solutions entières possibles
- Le point clé consiste à exploiter un résultat de 2016 sur les points de réseau pour abaisser la borne supérieure du covering radius, ce qui ramène le temps d’exécution à l’ordre de ((\log n)^{O(n)})
- L’approche n’est pas encore appliquée directement à des systèmes logistiques réels, mais elle s’approche presque de la limite théorique de vitesse pour l’ILP et indique une direction de long terme pour l’amélioration des solveurs en pratique
Pourquoi les contraintes entières rendent l’optimisation difficile
- Le problème du voyageur de commerce est un ancien problème de calcul qui consiste à trouver le plus court trajet passant par plusieurs villes, et vérifier tous les trajets possibles devient vite ingérable dès que le nombre de villes augmente un peu
- La programmation linéaire est un modèle mathématique qui traite de manière systématique les combinaisons possibles à l’aide d’équations et d’inégalités
- Dans les problèmes d’optimisation du monde réel, une réponse décimale est souvent inutilisable
- Dans un plan d’optimisation d’usine, une réponse demandant de produire 500,7 canapés est difficile à transformer en décision réelle
- La programmation linéaire en nombres entiers (ILP) est une variante de la programmation linéaire avec de telles contraintes d’intégralité, largement utilisée pour des décisions discrètes comme la planification de la production, les horaires d’équipage des compagnies aériennes ou le routage de véhicules
- Santosh Vempala considère l’ILP comme un outil central de la recherche opérationnelle, à la fois en théorie et en pratique
Des limites de vitesse qui n’ont que lentement progressé depuis les années 1980
- Depuis sa formulation il y a plus de 60 ans, plusieurs algorithmes ont été proposés pour l’ILP, mais en nombre d’étapes nécessaires, ils restaient globalement lents
- Le point de comparaison le plus simple est le cas de variables binaires qui ne peuvent prendre que 0 ou 1
- 1 variable donne 2 combinaisons possibles
- 2 variables en donnent 4
- 3 variables en donnent 8
- En général, le temps d’exécution augmente exponentiellement avec le nombre de variables, c’est-à-dire la dimension
- Quand les variables peuvent prendre des valeurs entières plus larges que 0 et 1, le temps d’exécution devient bien plus long
- Les chercheurs cherchent depuis longtemps à rapprocher l’ILP général de la vitesse de ce cas binaire plus simple
- Après le record des années 1980, il n’y a eu ensuite que des améliorations progressives
L’interprétation géométrique ouverte par Lenstra
- En 1983, Hendrik Lenstra a prouvé que le problème général de l’ILP pouvait être résolu et a proposé le premier algorithme correspondant
- Lenstra a reformulé l’ILP comme un problème géométrique
- Les inégalités d’un ILP sont représentées par une forme convexe, c’est-à-dire un corps convexe (convex body)
- L’intérieur de cette forme correspond à toutes les valeurs possibles qui satisfont les inégalités
- Un problème à 2 variables devient un polygone dans le plan, un problème à 3 variables devient un solide en 3D, et ainsi de suite quand la dimension augmente
- Tous les entiers peuvent être vus mathématiquement comme des points d’un réseau (lattice)
- En 2D, cela ressemble à une mer de points
- En 3D, cela prend la forme d’une structure comme les points de jonction d’une armature métallique
- Résoudre un ILP revient donc à trouver l’intersection entre un corps convexe et un réseau, c’est-à-dire l’endroit où les solutions possibles rencontrent des points entiers
- L’algorithme de Lenstra permettait d’explorer cet espace, mais pour gagner en efficacité il fallait parfois découper le problème en morceaux de plus faible dimension, ce qui augmentait le temps d’exécution
Le covering radius, goulot d’étranglement pendant 30 ans
- En 1988, Ravi Kannan et László Lovász ont cherché à traiter plus efficacement l’intersection entre corps convexes et réseaux grâce au concept de covering radius, issu des travaux sur les codes correcteurs d’erreurs
- Le covering radius est lié à la taille qui garantit qu’un corps convexe, placé n’importe où sur un réseau, contiendra au moins un point entier
- L’ampleur de cette valeur détermine en grande partie l’efficacité avec laquelle on peut résoudre un problème d’ILP
- Déterminer la taille idéale du covering radius était en soi un problème difficile
- Kannan et Lovász ont resserré l’intervalle des valeurs possibles avec des bornes supérieures et inférieures, en montrant que la borne supérieure croissait linéairement avec la dimension
- Mais ce seul résultat ne suffisait pas à réduire fortement le temps d’exécution de l’ILP, et les progrès sont restés limités pendant les 30 années suivantes
Le nouvel algorithme de Reis et Rothvoss
- Victor Reis et Thomas Rothvoss ont trouvé une percée en s’appuyant sur d’autres résultats mathématiques centrés sur les réseaux
- En 2016, Oded Regev et Noah Stephens-Davidowitz ont montré combien de points de réseau pouvaient se trouver à l’intérieur de certaines formes
- Reis et Rothvoss ont appliqué ce résultat à d’autres formes pour mieux estimer le nombre de points de réseau inclus dans le covering radius de l’ILP
- Cette estimation a abaissé la borne supérieure, ce qui a fortement réduit le temps d’exécution de l’algorithme ILP dans son ensemble
- Le nouveau temps d’exécution est ((\log n)^{O(n)}), où (n) est le nombre de variables et (O(n)) signifie une croissance linéaire en fonction de (n)
- Cette expression est considérée comme « presque » au même niveau que le temps d’exécution du problème à variables binaires
Entre avancée théorique et application concrète
- Noah Stephens-Davidowitz voit dans ce nouvel algorithme la première amélioration majeure d’un solveur ILP depuis près de 40 ans
- Daniel Dadush estime que ce résultat se situe au croisement des mathématiques, de l’informatique et de la géométrie
- Le nouvel algorithme n’a pas encore été utilisé pour résoudre des problèmes logistiques réels
- Mettre à jour les programmes actuels pour les adapter à cette approche demanderait encore beaucoup de travail
- Rothvoss estime que le point central de ce résultat est la compréhension théorique de problèmes ayant des applications fondamentales
- Il reste possible d’améliorer encore l’efficacité des calculs ILP, mais Vempala pense qu’il faudra des idées fondamentalement nouvelles pour se rapprocher davantage du temps d’exécution idéal
1 commentaires
Avis sur Hacker News
Abaisser la borne supérieure algorithmique d’un problème NP-complet fondamental est toujours très intéressant, mais cela ne veut pas forcément dire que le problème se résoudra plus vite dans les implémentations réelles.
Les solveurs de programmation en nombres entiers mixtes (MIP) combinent de nombreux algorithmes et une grande quantité d’heuristiques ; l’accumulation de bibliothèques d’heuristiques et de stratégies est la raison principale pour laquelle les progrès des solveurs MIP ont dépassé la loi de Moore.
Selon https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., entre 1990 et 2014, l’amélioration du matériel a représenté un facteur 6 500, tandis que l’amélioration logicielle a contribué à un gain de performance d’un facteur 870 000.
Cet article peut lui aussi devenir une pièce du puzzle qui continuera à améliorer les performances des solveurs MIP, mais ce n’est pas garanti.
Je ne comprends pas bien l’explication selon laquelle le nouvel algorithme ne serait pas encore utilisé pour résoudre des problèmes de logistique parce que « mettre à jour les programmes actuels demanderait trop de travail ».
La plupart des modèles propres à un domaine appellent des solveurs comme Gurobi, CPLEX ou FICO pour les gros problèmes, et des solveurs open source comme SCIP pour les petits.
On peut échanger des modèles entre ces solveurs via le format MPS standard ; la formulation du problème ne change pas, seule la méthode de résolution interne du solveur devrait changer, non ?
Si cela signifie qu’il faut une nouvelle implémentation, alors le bénéfice pour le monde une fois celle-ci réalisée pourrait être énorme.
Ces outils sont des produits d’ingénierie extrêmement complexes, bâtis sur des décennies d’améliorations incrémentales ; rien que comprendre comment intégrer une nouvelle découverte dans ces moteurs demanderait sans doute un effort de recherche considérable.
Il existe bien des façons standard d’échanger des formulations de problèmes avec des formats comme MPS, et aujourd’hui les langages de modélisation algébrique comme AMPL semblent plus courants, mais ces formats ne fournissent qu’une formulation mathématique standard.
La résolution effective est très spécifique à chaque solveur, avec ses propres structures de données, algorithmes et heuristiques.
Ils ne sont pas interchangeables, ne sont pas volontairement publiés, et on ne peut pas insérer quelques nombres externes au milieu du processus sans connaître le code du solveur et l’ensemble de son fonctionnement.
Je voulais dissiper ce malentendu.
Dans la mesure du possible, j’évite d’avoir à implémenter directement des choses avec eux.
Cela n’enlève rien au fait que c’est un excellent résultat.
Du point de vue de la complexité théorique du calcul, les meilleurs algorithmes pour la « programmation linéaire en nombres entiers » [2] reposent sur les réseaux, et offrent les meilleures complexités en grand O dans le pire cas.
Mais les implémentations actuelles ont généralement besoin (1) d’arithmétique rationnelle en précision arbitraire, comme avec gmplib [3], ce qui consomme beaucoup de mémoire et est aussi lent en pratique, et (2) d’étapes de réduction de réseaux de type LLL [4], qui n’exploitent pas la parcimonie des matrices.
Résultat : ces algorithmes ne tiennent généralement pas en mémoire et ne peuvent même pas démarrer sur des problèmes matriciels plus grands que 1000x1000 ; et même lorsqu’ils tiennent, ils sont beaucoup trop lents.
Les solveurs de programmation en nombres entiers utilisés en pratique reposent plutôt sur le branch and bound, un algorithme de retour arrière similaire à ceux employés pour résoudre SAT, et résolvent à chaque itération un problème de « programmation linéaire » obtenu en remplaçant toutes les variables du problème initial par des variables continues.
Chaque problème de programmation linéaire peut être résolu par des algorithmes en temps polynomial comme les méthodes de points intérieurs, mais en pratique on utilise la méthode du simplexe, dont le temps est exponentiel dans le pire cas.
La raison est que les problèmes de programmation linéaire à résoudre sont très similaires les uns aux autres, et que le simplexe exploite bien cela en pratique.
Les algorithmes associés exploitent aussi fortement la parcimonie des vecteurs et des matrices.
C’est pourquoi certaines personnes résolvent des problèmes de programmation en nombres entiers avec des millions de variables en quelques jours, voire en quelques heures.
Les implémenteurs de solveurs ne cherchent pas la meilleure complexité théorique absolue ; on peut dire que la théorie et la pratique de l’optimisation discrète ont, dans une certaine mesure, divergé.
Cela dit, l’article de Reis & Rothvoss [1] est un travail mathématique profond et, pour quiconque s’intéresse aux mathématiques discrètes, il est très impressionnant en soi.
Il résout une conjecture de Dadush vieille de dix ans et a été présenté en novembre dernier à FOCS, l’une des deux grandes conférences de référence en informatique théorique.
L’utilité pratique directe n’est pas l’essentiel, et les auteurs l’admettraient probablement dans un cadre informel.
Bien sûr, ils diraient autre chose dans une demande de financement de recherche, mais cela fait partie du jeu.
Cela ne veut pas dire que c’est inutile : faire progresser les connaissances mathématiques a déjà une grande valeur, et des chercheurs des générations futures pourraient s’appuyer sur ces idées pour créer des algorithmes pratiques qui repousseront l’état de l’art des solveurs.
Au final, ces algorithmes ont tous un temps exponentiel dans le pire cas.
En théorie, on cherchera à réduire un peu le polynôme dans l’exposant de la complexité en pire cas, mais en pratique on veut généralement résoudre un seul gros problème d’optimisation, pas une famille de problèmes dont la taille n augmente.
Ce qui compte, ce n’est pas tant la pente de la courbe de croissance du temps de résolution que la capacité à résoudre la grande instance qu’on a devant soi ; et cette instance possède généralement une structure qui l’empêche d’être un pire cas parmi celles de même taille.
Les choix d’ingénierie sont donc différents.
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
Le résumé est plus instructif : https://arxiv.org/abs/2303.14605
Il indique qu’ils ont obtenu un algorithme aléatoire en temps (log(2n))^O(n) pour résoudre la programmation entière à n variables.
Autrement dit, il s’agit d’un résultat théorique : en s’appuyant sur l’analyse de la structure des corps convexes dans R^n et de la façon de les recouvrir par un réseau entier, il propose un algorithme en temps exponentiel meilleur que le meilleur précédent.
La plupart des travaux pratiques en ILP utilisent des heuristiques et la méthode de séparation et évaluation, et exploitent la structure particulière de certaines formulations de problème.
Il n’est pas clair que cette recherche aide l’un ou l’autre de ces aspects ; sans explication de quelqu’un de chez Gurobi, par exemple, il me semble difficile d’en juger à la seule lecture de l’article.
Détail mineur, mais le titre devrait préciser programmation linéaire en nombres entiers.
Ici, la partie « nombres entiers » fait une bien plus grande différence.
Pour la programmation linéaire, on connaît des algorithmes en temps polynomial depuis des décennies, tandis que la programmation linéaire en nombres entiers est NP-difficile.
La programmation linéaire continue est difficile elle aussi.
Pas au sens où elle serait NP-difficile, mais au sens où construire des solveurs LP modernes efficaces demande beaucoup d’algorithmique et d’ingénierie.
Rien que le calcul numérique est déjà suffisamment complexe.
Et de nombreux solveurs de programmation linéaire en nombres entiers reposent sur des solveurs de programmation linéaire continue.
Si vous êtes ingénieur logiciel et que vous vous intéressez au machine learning ou aux algorithmes, la programmation linéaire vaut la peine d’être apprise.
Un nombre étonnant de problèmes peuvent être formulés comme de l’optimisation linéaire.
Par exemple, à l’université, j’ai discuté avec un ami qui étudiait le génie industriel du nombre moyen minimal d’échanges nécessaires pour placer des boules de billard dans des positions de départ admissibles à l’intérieur du triangle de rack.
Nous avons tous les deux écrit un programme pour le résoudre par échantillonnage de Monte-Carlo : ma solution faisait un BFS dans l’espace d’états du graphe, tandis que la sienne utilisait la programmation linéaire.
Je pense que la sienne était probablement plus efficace.
Par exemple, l’arbre couvrant de poids minimal, le couplage dans les graphes bipartis ou généraux, les flots de réseau, l’intersection de matroïdes, les flots sous-modulaires, etc.
Les solutions aux sommets de certains LP ont aussi des propriétés intéressantes exploitables pour concevoir des algorithmes d’approximation pour des problèmes NP-complets.
Par exemple, on peut démontrer que, dans une solution au sommet du problème de Steiner forest, il existe toujours une variable de valeur au moins 1/2 ; en arrondissant les variables de façon itérative et en résolvant à nouveau le LP, on obtient donc un algorithme d’approximation à facteur 2.
À l’époque où j’étais en master/doctorat, c’était le seul algorithme d’approximation à facteur 2 connu pour ce problème.
Autre point intéressant : avec seulement un oracle de séparation en temps polynomial, on peut résoudre un LP même s’il comporte un nombre exponentiel de contraintes.
C’était vraiment amusant, et je le recommande.
Même aujourd’hui, du côté de la recherche opérationnelle, il y a une quantité surprenante de recouvrements, mais je suis choqué par le nombre de diplômés en génie industriel qui ne savent pas vraiment programmer.
C’est vraiment dommage.
Comme on ne pouvait généralement trader que des montants entiers au centime près, je me souviens que la partie entière était assez importante.
Article court mais bon.
Je n’ai pas encore creusé les maths, mais le preprint semble être celui-ci : https://arxiv.org/pdf/2303.14605.pdf
Ils ne semblent pas considérer directement les groupes d’espace comme moyen de simplifier le problème en généralisant son « espace » par réduction des symétries ou des répétitions, mais il serait intéressant de voir si ce type de structure pourrait s’appliquer.
Comme j’utilise des logiciels qui appliquent des groupes d’espace et décrivent les cellules de Voronoï autour de points, ou d’ensembles de points, distribués à l’intérieur, je connais bien la manière « inquiétante » dont les effets se propagent [1].
Je ne suis pas mathématicien, seulement architecte, donc ce domaine dépasse mes compétences, mais en tant que personne qui observe des trajectoires traversant des structures en nid d’abeilles générées, ce résultat mérite d’être étudié plus avant.
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Si vous connaissez un mathématicien avec qui collaborer sur ce type de travail, j’aimerais que vous me contactiez.
C’est un travail en cours et, comme je l’ai dit, les aspects mathématiques dépassent mes compétences, mais je suis tombé sur des propriétés intéressantes qu’un véritable spécialiste aurait intérêt à examiner de plus près.
À propos du problème du voyageur de commerce, une citation du dernier livre de Sapolsky, Determined: A Science of Life without Free Will, est intéressante
Je ne sais pas à quel point c’est pertinent pour les développeurs logiciels, mais c’est fascinant
Quand une fourmi cherche de la nourriture en inspectant huit emplacements, idéalement elle ne devrait visiter chaque endroit qu’une seule fois et choisir le plus court des 5 040 itinéraires possibles, c’est-à-dire 7!
C’est une forme du célèbre problème du voyageur de commerce, sur lequel les mathématiciens butent depuis des siècles sans trouver de solution générale
Une stratégie consiste à examiner tous les itinéraires possibles et à les comparer pour choisir le meilleur, par force brute ; mais avec seulement 10 lieux à visiter, il y a déjà plus de 360 000 possibilités, et avec 15, plus de 80 milliards
Or, si l’on lâche les quelque 10 000 fourmis d’une colonie typique sur un problème à huit points de nourriture, même si aucune fourmi ne connaît autre chose que le chemin qu’elle a emprunté et deux règles, elles trouvent en un temps bien plus court que la force brute une solution presque optimale parmi les 5 040 possibilités
Cette approche fonctionne si bien que des informaticiens résolvent aussi ce type de problèmes avec des « fourmis virtuelles » ; c’est ce qu’on appelle aujourd’hui l’intelligence en essaim
Et la réaction standard est : « des algorithmes informatiques très simples font aussi cela »
Pour le problème du voyageur de commerce avec distance euclidienne — c’est-à-dire lorsque chaque nœud a des coordonnées fixes et que le coût d’un trajet est la distance euclidienne entre deux points —, on peut même donner un algorithme en temps polynomial qui trouve un chemin à un facteur ε près de l’optimum
Cela dit, il est exponentiel en ε
La préface contient aussi une excellente clause de non-responsabilité
« Nous pensons personnellement que la littérature du domaine devrait contenir moins de marsupiaux et plus de mathématiques, et qu’en tant que communauté nous devrions dépasser cette période riche en métaphores, un peu comme la chimie a dépassé l’alchimie. Cependant, cette liste ne prétend rien quant à la qualité scientifique des articles qui y figurent. »
[1]: https://fcampelo.github.io/EC-Bestiary/
C’est un algorithme modélisé sur ce comportement des colonies de fourmis
Comme d’autres l’ont dit, il est utile pour trouver des optima locaux, comme la recherche tabou, le recuit simulé ou les algorithmes génétiques
Pour la plupart des objectifs métier, comme l’exemple de « production de canapés » dans l’article, cela suffit
Mais ce n’est pas la même chose que trouver une « solution générale »
La comparaison que fait Sapolsky entre notre difficulté à trouver des « solutions générales » et la capacité des fourmis à trouver des optima locaux me semble un peu trompeuse
Cela ne veut pas dire que la forme générale du problème n’est pas NP-difficile, mais qu’en ajoutant davantage d’informations on peut approximer une solution suffisamment bonne, ou rendre la recherche optimale traitable
Cette perspective était particulièrement marquée lors de la première « révolution » de l’IA, où il était courant de voir l’IA comme un problème de recherche enrichi par des connaissances humaines
Est-ce cela que le livre entend par « intelligence en essaim » ?
Beaucoup de problèmes d’optimisation discrète peuvent être traduits en programmation linéaire
Comme les solveurs SAT, c’est un outil vraiment puissant à connaître
En tant que développeur, ça a été l’un de ces moments où l’on se dit : « comment ai-je pu passer à côté jusqu’ici ? »
C’est un excellent résultat, mais il ne sera probablement pas pratique
C’est un peu comme en programmation linéaire : les méthodes de points intérieurs ont une meilleure complexité théorique que le simplexe, mais dans la réalité un simplexe bien réglé gagne presque toujours
Existe-t-il une « raison » largement admise au fait que les méthodes de points intérieurs sont généralement plus lentes en pratique ?
Passer par l’intérieur semblerait permettre d’atteindre plus vite une bonne solution que de rester collé à la frontière, mais peut-être que cette différence compte moins en haute dimension
La formulation employée ici me paraît un peu confuse
Il y a une phrase disant que « la meilleure version qu’ils aient imaginée, une sorte de limite de vitesse, vient du cas trivial où les variables du problème ne peuvent prendre que des valeurs binaires, 0 ou 1, comme le fait qu’un voyageur de commerce visite ou non une ville » : est-ce qu’ils appellent un problème NP-complet un cas trivial ?
Je pensais que tout ILP pouvait être réduit à un 01-ILP, et réciproquement
Et avec le passage « malheureusement, lorsque les variables prennent des valeurs au-delà de 0 et 1, le temps d’exécution de l’algorithme devient beaucoup plus long. Les chercheurs se demandent depuis longtemps s’il est possible de se rapprocher de cet idéal trivial », je me demande si cette recherche est un solveur qui améliore la borne inférieure du 01-ILP, ou bien un algorithme qui rapproche la frontière entre 01-ILP et ILP général