Nous suivons la recherche en optimisation et contribuons à l'open source

L'optimisation est née d'un problème de planification en temps de guerre avant de devenir une discipline. La méthode du simplexe arrive en 1947, et les quinze années qui suivent produisent l'essentiel de la machinerie encore en service : programmation dynamique, plans sécants, séparation et évaluation, plus courts chemins, et les décompositions qui permettent de résoudre un grand problème comme une suite de petits.

Puis Karp montre, en 1972, pourquoi le travail ne serait jamais terminé. Toute une famille de problèmes de planification ordinaires n'a aucun algorithme exact efficace connu, et aucun n'a été trouvé depuis. La réponse n'a pas été un meilleur algorithme, mais beaucoup, empruntés partout où on pouvait les prendre : le recuit simulé à la métallurgie, la recherche tabou à l'idée d'une mémoire courte, les algorithmes génétiques et l'optimisation par colonies de fourmis à la biologie, la programmation par contraintes à la logique, et la recherche à grand voisinage au constat qu'un bon plan est presque toujours à une petite retouche d'un meilleur.

Aucune ne l'a emporté, et c'est tout l'intérêt. Chacune est forte sur une forme de problème que les autres traitent mal, si bien que le domaine les a toutes gardées et a appris à les combiner : recherche exacte guidée par des heuristiques, propagation de contraintes adossée à l'apprentissage de clauses, et depuis peu des décisions de branchement apprises sur des données. Ces dernières années ont ajouté les méthodes du premier ordre et les GPU, qui rouvrent des programmes linéaires à des tailles pour lesquelles le simplexe n'a jamais été conçu.

Julia est le langage dans lequel s'écrit une grande partie de la recherche actuelle en optimisation. Il tourne à la vitesse dont les solveurs ont besoin et se lit au plus près des mathématiques, si bien qu'un article et son implémentation restent visiblement la même chose.

JuMP se pose par-dessus. Décrivez un problème une seule fois, dans une syntaxe proche des mathématiques, puis confiez-le à l'un des plus de 30 solveurs derrière une interface unique. C'est le standard de fait dans la communauté Julia et la colonne vertébrale de la recherche en optimisation dans les universités européennes, dont l'UCLouvain, où une partie de notre équipe s'est formée.

Nous y travaillons, et pas seulement avec. Des membres de l'équipe proposent des pull requests sur les paquets centraux, maintiennent des interfaces de solveurs et présentent à l'atelier JuMP-dev.

Construit sur