Dans un premier article, j’ai parlé de l’approche hybride ML et OR (Machine Learning et Operations Research). Il s’agit d’une série d’articles où j’explique pourquoi cette approche hybride est nettement supérieure. Dans cet article, je développe l’efficacité de l’optimisation.
On entend souvent parler de projets qui ont été optimisés par du ML (par exemple DeepMind AI Reduces Google Data Centre Cooling Bill by 40%). Pour quelqu’un qui n’y connaît rien, il est bien tentant de croire qu’il s’agit d’une bonne idée. Il n’en est rien comme l’indique le titre de cet article. Ce n’est pas le cas. Du tout.
Prenons le PVC (Problème du Voyageur de Commerce) plus connu sous le nom de TSP (Travelling Salesman Problem). C’est sans doute le problème le plus étudié en recherche opérationnelle. Le but de ce problème est de déterminer une tournée complète qui passe une seule fois par chaque ville et ce pour un coût minimal (distance minimale, temps minimal…). C’est un exemple typique de problèmes NP-difficiles, c’est-à-dire un problème qui même avec un super ordinateur ou des ordinateurs en parallèle ne se résout pas aisément. C’est un problème qui se résout en machine learning (voir par exemple Learning TSP requires rethinking generalization) mais mal jusqu’à présent. Prenons la résolution exacte, c’est-à-dire la recherche d’une solution optimale (avec preuve d’optimalité). Pour autant que je sache, les meilleures approches en ML peuvent résoudre ce problème avec des instances d’environ 100 villes. C’est pas mal mais un étudiant en recherche opérationnelle de première année recevrait un F ou un 0/20 pour un tel résultat ! En effet, en recherche opérationnelle, les meilleures approches (Concorde, voir Certification of an optimal TSP tour through 85,900 cities) peuvent résoudre ce problème exactement avec environ… 100 000 villes ! Et l’on parle d’un problème NP-difficile! Ce qui veut dire que si vous avez un algorithme pour résoudre le TSP avec 100 villes et que vous aimeriez résoudre le problème avec 120 villes… vous allez sans doute devoir changer d’algorithme ! 100 versus 100 000 ! Cela donne le vertige.
Il ne faut pas abandonner la voie du machine learning pour autant mais au lieu de vouloir réinventer la roue, il faudrait sans doute mieux reprendre ce qui se fait en recherche opérationnelle et y ajouter du machine learning. Encore faut-il savoir comment le faire… mais ce sera le sujet d’un autre article !
Ce que j’ai présenté pour le TSP est en fait valide pour tous les problèmes combinatoires, jusqu’à présent en tout cas.
Une dernière chose, on reproche souvent à la recherche opérationnelle d’être lente. En effet, il faut parfois des heures voire des jours ou même des semaines pour obtenir une solution. Mais j’aimerais attirer l’attention sur le fait que tout d’abord, on n’a pas forcément besoin d’une solution optimale ou d’une solution avec preuve d’optimalité. Ensuite, il existe des techniques pour faire de l’optimisation en temps réel. Tout dépend ce que l’on cherche et si l’on veut une solution avec preuve d’optimalité, cela a un coût…
