Métaheuristique et programmation mathématique

点击翻译按钮获取中文摘要

Dans notre programme de recherche, nous nous intéressons à résoudre plusieurs applications dans divers domaines. Nous utilisons deux types de méthodes de résolution : des méthodes exactes et des hybrides de métaheuristiques. Pour les méthodes exactes, il est possible d'exploiter la structure des problèmes afin d'ajouter ou de modifier des contraintes pour améliorer les bornes inférieures dans l'arbre d'énumération implicite. Pour d'autres problèmes de grande taille s'échelonnant sur un horizon de plusieurs périodes, nous utilisons la décomposition en horizon roulant pour résoudre plusieurs problèmes plus petits afin de fixer séquentiellement les valeurs des variables. Finalement pour d'autres problèmes mixtes de grande taille, nous utilisons la décomposition de Benders. Les hybrides que nous utilisons combinent plusieurs métaheuristiques. En général, un hybride repose sur une recherche locale (méthode Tabu, recuit simulé) ou une recherche avec population (algorithme génétique, « scatter search »). Le mécanisme d'amélioration (intensification) combine différents processus. Le choix de celui retenu à une itération spécifique repose sur un processus d'apprentissage évaluant leur performance jusqu'ici. Le mécanisme de diversification génère de nouvelles solutions initiales en utilisant des méthodes heuristiques ou des mécanismes de recombinaison comme ceux des algorithmes génétiques ou du « scatter search ». En programmation mathématique, nous nous intéressons à la résolution exacte du problème de formation de cellules (un problème fractionnaire en nombres entiers) avec la méthode de Dinkelbach, afin de vérifier la qualité des solutions obtenues avec des métaheuristiques. Nous étudions aussi l'approche « Resolution Search » pour résoudre les problèmes combinatoires en nombres entiers. Cette méthode d'énumération implicite parcoure le domaine réalisable d'une façon différente de celle des méthodes Branch & Bound.