- La programmation linéaire en nombres entiers mixtes (MILP) s'est imposée comme un outil central dans de nombreux secteurs industriels
- Grâce aux progrès de l'efficacité de calcul des solveurs modernes, il est désormais possible de trouver rapidement une solution optimale à des problèmes autrefois difficiles à résoudre
- Cet article se concentre sur les récents progrès pratiques des méthodes de résolution MILP ainsi que sur les améliorations des performances de calcul
- Parmi les principales méthodologies présentées figurent le branch-and-cut, la décomposition de Dantzig-Wolfe et la décomposition de Benders
- Il résume également les défis persistants du domaine MILP et les opportunités pour les recherches futures
Introduction
- La programmation linéaire en nombres entiers mixtes (MILP) est un outil essentiel de la recherche opérationnelle, utilisé avec succès dans de nombreux domaines industriels
- Les solveurs MILP modernes peuvent désormais trouver en quelques secondes une solution optimale à des problèmes de grande taille qui étaient autrefois impossibles à traiter
- Cela a entraîné une extension de l'usage du MILP dans de nombreux secteurs, notamment le transport, la supply chain, le revenue management, la finance, les télécommunications et l'industrie manufacturière
- Mais il subsiste encore des problèmes non résolus et de nouveaux défis, ce qui fait de la recherche sur le MILP un domaine toujours très actif
Aperçu des points principaux
- Cet article analyse les développements récents des méthodes de résolution MILP et les améliorations de leurs performances pratiques, en examinant concrètement la contribution de chaque technique aux gains de performance informatique
- Parmi l'abondante littérature, il privilégie les travaux fondés sur de véritables expériences de calcul
- La discussion s'organise autour de trois domaines clés des méthodes MILP
- Méthode branch-and-cut : approche représentative de résolution MILP combinant la séparation en nœuds et les techniques de plans de coupe
- Décomposition de Dantzig-Wolfe : approche de décomposition qui divise les grands problèmes en sous-problèmes plus petits pour les traiter efficacement
- Décomposition de Benders : méthode qui réduit la charge de calcul dans des structures complexes en séparant variables et contraintes puis en les résolvant de manière itérative
Conclusion : défis et perspectives d'avenir
- La dernière partie de l'article passe en revue les défis qui subsistent pour le MILP ainsi que les opportunités de recherche futures
- La complexification des problèmes industriels réels, le passage à l'échelle des données et les limites de performance des solveurs constituent les principaux thèmes de recherche à venir
- Le domaine du MILP devrait continuer à se développer avec les progrès algorithmiques, les avancées matérielles et l'élargissement de nouveaux domaines d'application
1 commentaires
Commentaire Hacker News
Quelqu’un se demande si quelqu’un pourrait expliquer une bonne fois pour toutes pourquoi des solveurs ILP commerciaux comme Gurobi sont tellement meilleurs que les solveurs gratuits/open source, et demande si cela tient à la difficulté intrinsèque de l’ILP, ou au fait que les meilleurs solveurs ne sont qu’un vaste ensemble d’heuristiques pour certains sous-problèmes, de sorte que les stratégies généralement « bonnes » ne sont toujours pas dans le domaine public
Les solveurs commerciaux travaillent généralement en étroite collaboration avec leurs clients pour implémenter des techniques d’accélération spécifiques aux problèmes, et disposent d’un savoir-faire accumulé sur 10 à 20 ans ; en MILP, ils s’appuient sur de bonnes heuristiques (choix des points de départ pour branch-and-bound, élagage efficace de l’arbre) et des coupes personnalisées (pour exclure efficacement des solutions partielles), et l’on souligne aussi que lorsque des chercheurs en OR choisissent eux-mêmes leurs problèmes et écrivent des coupes et heuristiques sur mesure, ils peuvent souvent obtenir de meilleurs résultats que les solveurs commerciaux ; mais les éditeurs de solveurs embauchent des équipes de recherche de niveau doctorat pour implémenter cela de manière cohérente et suivre les améliorations sur d’innombrables données réelles de clients
Les solveurs commerciaux peuvent investir énormément de temps et de ressources dans le réglage de la performance, parce que de vrais clients s’y intéressent et les aident ; au-delà des heuristiques, cela inclut aussi l’identification de sous-problèmes simples ou de problèmes approchés, puis la réinjection de ces résultats dans le problème global ; les solveurs open source sont limités parce que (1) la barrière à l’entrée pour développer un optimiseur moderne est très élevée (peu de personnes maîtrisent à la fois les maths et le code), (2) si l’on a ce niveau de compétence, on part généralement vers une carrière beaucoup mieux rémunérée, et (3) la structure de l’open source fait que les clients fournissent rarement des cas d’amélioration, des données de performance ou du profiling, ce qui expose vite ses limites Il existe des exceptions, comme SNOPT, qui est commercial mais développé de manière commerciale non traditionnelle ; les solveurs académiques sont souvent concentrés sur un domaine applicatif donné et donc peu généralistes ; dans d’autres secteurs, de grandes entreprises comme Google rachètent ou soutiennent des projets pour faire grandir l’écosystème, mais dans le domaine des solveurs, l’investissement nécessaire pour construire toute la stack dès le départ est trop lourd
Les solveurs commerciaux peuvent vraiment déterminer, grâce à une grande variété d’astuces et de mécanismes de détection de motifs, quelles astuces seront efficaces selon le problème ; si l’on connaît bien la structure du problème, on peut faire mieux qu’un solveur commercial, mais sur un problème aléatoire il y a très peu de chances
Quelqu’un avance l’idée que « solveur = ensemble varié d’heuristiques pour des sous-problèmes spécialisés », et une réponse fait remarquer que presque tout problème NP-hard a cette structure ; l’ILP est équivalent au SAT, donc cela s’applique de la même manière
Question d’échelle commerciale et de vitesse : la plupart des sociétés de trading quant exécutent de très gros problèmes d’optimisation aussi souvent que possible, et les solveurs open source échouent souvent tout simplement à résoudre le problème, ou rencontrent des problèmes de mémoire, ce qui illustre l’ampleur de l’écart
Souvenir d’avoir construit un outil d’allocation de ressources avec la bibliothèque MILP ILOG d’IBM : si l’on avait dû résoudre un problème similaire il y a 20 ans, on y serait encore alors qu’aujourd’hui cela prend 5 minutes ; les ordinateurs sont devenus mille fois plus rapides, et les algorithmes aussi mille fois meilleurs, soit au total un gain d’un facteur un million ; un bon rappel à méditer quand on fait des prédictions sur l’avenir ; au passage, ici les « ressources » étaient des diamants
Question sur les usages concrets : avec les limites habituelles des approches pilotées par les données en optimisation numérique (fiabilité, problèmes de données, etc.), est-ce qu’au final ce n’est pas souvent une personne importante qui décide « à l’intuition » ?
Dans une entreprise, des solveurs sont utilisés sur toute la stack : optimisation de la planification des batteries domestiques et des EV, planification optimale sur un portefeuille de plusieurs centaines de milliers de foyers, puis même trading de ce portefeuille via des solveurs ; les prix spot européens de l’électricité sont eux aussi déterminés en exécutant un unique solveur géant appelé Euphemia ; dès qu’il existe un objectif d’optimisation clair directement relié à l’argent, les solveurs sont largement utilisés en pratique
Exemple concret dans une entreprise FMCG : (1) planification des commerciaux et des tournées de livraison, (2) ordonnancement des machines, de la main-d’œuvre et des matériaux pour la production, (3) détermination des niveaux de stock appropriés dans les entrepôts et centres de distribution, etc. ; ce n’est pas entièrement automatisé à cause de la difficulté de la prévision de la demande
Partage de liens vers des études de cas utiles : études de cas Gurobi, études de cas CPLEX, études de cas Hexaly (ex-LocalSolver)
Quelqu’un dit avoir entendu que Gurobi est assez cher, et demande si des informations réelles sur les prix peuvent être partagées
Les prix précis ne sont pas publics, mais pour pratiquer le MIP il est recommandé de ne pas acheter de solveur commercial comme XPRESS/Gurobi/CPLEX et de plutôt utiliser une licence étudiante gratuite ou un solveur MIP open source gratuit pour usage non commercial, comme HiGHS ou SCIP
D’après ce qui a été entendu, la tarification se fait au niveau du « appelez-nous pour négocier », avec des montants ajustés en fonction de combien le client gagne réellement grâce à cela
On souligne que c’est bien moins coûteux que des décisions lentes et sous-optimales ; pour les petits problèmes, un solveur gratuit (GLPK, etc.) suffit, mais pour les gros problèmes réels en entreprise, obtenir une réponse à temps est quasiment impossible autrement, donc les solveurs premium valent largement leur prix
Il y a une dizaine d’années, quelqu’un se souvient d’un ordre de grandeur d’environ 100 000 dollars pour une licence couvrant plusieurs serveurs ; il ne se rappelle plus le nombre exact d’utilisateurs ou de serveurs, mais précise que l’industrie considère clairement que cela les vaut
Gurobi propose aussi un service cloud facturé à l’heure, et les licences non académiques sont très chères
Retour d’expérience d’avoir implémenté soi-même des hyperplans de coupe de Gomory dans les années 1990, avec surprise face aux progrès du domaine ; autrefois il fallait deux mois pour résoudre un problème LP, maintenant une seconde suffit ; un ouvrage de Bixby rapporte qu’entre 1990 et 2020, CPLEX et Gurobi sont devenus près de 4 millions de fois plus rapides, indépendamment des performances matérielles
Entre 1988 et 2004, le matériel est devenu 1 600 fois plus rapide et les solveurs LP 3 300 fois plus rapides, soit déjà plus de 5 millions de gain cumulé ; entre 2001 et 2020, les solveurs MILP commerciaux ont aussi gagné plus d’un facteur 1 000 (50 pour les algorithmes, 20 pour les ordinateurs) ; quelqu’un se demande s’il serait intéressant de collecter ce type de données d’accélération par domaine et de les décomposer entre contribution algorithmique et contribution matérielle ; en compilation, on cite aussi des résultats comme la « loi de Proebsting », selon laquelle les progrès des compilateurs apportent l’équivalent d’un doublement de la puissance de calcul tous les 18 ans
Impression que les approches ML/IA sont étonnamment peu utilisées sur ce type de problèmes ; il existe des articles qui tentent d’utiliser RL/GNN sur de petits problèmes, mais au final acheter une licence Gurobi semble rester la meilleure option ; quelqu’un dit avoir vu aussi des cas de RL dans l’optimisation d’ordonnancement récente, mais avec des performances réelles insuffisantes ; sur les gros problèmes, les algorithmes évolutionnaires semblent préférables ; au final, si l’on peut bien formuler le problème, l’approche OR paraît la plus efficace
Cela dépend du type de problème ; par exemple, la décision ON/OFF de centrales électriques (unit commitment) est extrêmement complexe, mais un solveur MILP peut trouver rapidement une solution globalement optimale ; un algorithme génétique n’offre aucune garantie d’échapper à un minimum local et peut être lent à exécuter, tandis qu’un réseau de neurones restera toujours sous-optimal
Le SAT est un problème classique de la GOFAI, et l’on peut écrire des solveurs SAT dans n’importe quel langage de la famille ML ; en ce sens, les approches « ML/IA » sont tout à fait applicables
Commentaire suggérant qu’il serait bien d’ajouter la mention pdf dans le titre
Le lien en question ne mène pas à un pdf mais à un résumé
Référence ajoutée vers le pdf de l’article : https://inria.hal.science/hal-04776866v1/document
Avis selon lequel l’integer linear programming ne paraît pas si complexe
Le problème de 3-coloration des sommets d’un graphe (G3C) est dans NP et NP-hard, donc NPC ; il existe un résultat montrant que résoudre un ILP général permet aussi de résoudre G3C ; et comme SAT est également NP-complet, résoudre SAT permet aussi de résoudre G3C, donc si l’on peut résoudre G3C on peut aussi faire de la factorisation entière (FAC) ; FAC n’est pas NPC mais reste extrêmement important dans l’informatique actuelle ; on peut donc en déduire qu’un ILP arbitraire est un problème très difficile ; ce qui embrouille souvent les gens, c’est que pour les problèmes NPC, les instances aléatoires sont en général faciles à résoudre, et la proportion d’instances vraiment dures tend même à diminuer à mesure que la taille augmente
Le problème du voyageur de commerce (Travelling Salesperson Problem, TSP) peut lui aussi être encodé en ILP, ce qui suggère déjà un niveau de difficulté considérable
Il faut trouver les entiers qui satisfont le mieux les contraintes ; cela ressemble à un problème sur les réels, mais c’est fondamentalement totalement différent ; il n’existe pas de méthode générale, seulement de (très bonnes) heuristiques pour des cas particuliers
C’est un problème plus difficile que la programmation linéaire
Ou alors on peut le voir comme un problème très concret