Efficacité des heuristiques de branchement pour le branch-and-bound multi-objectif : vers une gestion plus dynamique

National audienceLes problèmes d'optimisation combinatoire multi-objectif sont réputés pour être particulièrement difficiles à résoudre efficacement. Parmi les approches de résolution possibles, les algorithmes de branch-and-bound sont largement utilisés comme méthodes exactes, fondées sur un parcours arborescent de l’espace des solutions. Une des principales composantes de ces algorithmes est la stratégie de branchement, qui sélectionne à chaque étape de séparation la variable à instancier dans les sous-problèmes résultants. Pour un problème donné, il existe généralement plusieurs heuristiques de choix de la variable de séparation, les performances de ces heuristiques peuvent différer d'une instance à l'autre et il n'est souvent pas possible de définir une heuristique qui s’avère la plus performante sur l’ensemble des instances (cf. No Free Lunch Theorems). Classiquement les algorithmes de branch-and-bound appliquent une seule heuristique, fixe toute au long de la résolution..Dans ce travail nous cherchons à déterminer si l'application conjointe de plusieurs heuristiques lors d'une même résolution permet d'augmenter l'efficacité de l'algorithme. Nous nous intéressons plus particulièrement aux stratégies de branchement pour le problème du sac-à-dos binaire bi-objectif. Les heuristiques de branchement pour ce problème sont nombreuses, considérant soit un seul des objectifs, soit un compromis des deux objectifs. Dans un premier temps, nous tentons de mettre en évidence les forces et faiblesses de ces différentes heuristiques en fonction des instances, dans le but d'élaborer une stratégie statique mêlant plusieurs heuristiques. La diversité des instances rend cette tâche particulièrement difficile. Toutefois, nous sommes parvenus à montrer que la combinaison de différentes stratégies de branchement permet de réduire la taille de l'arbre de recherche. Nous avons ensuite défini des mesures de qualité pour ces heuristiques, que nous utilisons via un mécanisme d’apprentissage automatique pour sélectionner dynamiquement la stratégie de branchement à chaque séparation au cours du processus de branch-and-bound. Finalement, nous comparons l'efficacité de ce nouvel algorithme par rapport à l'emploi d'une stratégie unique de séparation et analysons les différents réglages de cette approche adaptative