Résolution en variables 0-1 de problèmes combinatoires de grande taille par la méthode tabou
Institution:
AngersDisciplines:
Directors:
Abstract EN:
Tabu search is an approximate method that is known to perform well for many combinatorial problems. In this thesis, we seek to enhance this meta-heuristic for the efficient solution of large-scale problems. To do so, we exploit three complementary and interrelated approaches. First, we propose to enrich the local taboo feature by combining it with global methods, such as linear programming and exhaustive enumeration. Secondly, we give a very important role to constraints in the design of features such as the neighbourhood, the motion heuristic and even the general mechanism of exploration of the search space. Third, we introduce an efficient implementation of the algorithm in a binary problem formulation. We experiment with this approach on three challenging problems of increasing size and complexity: multidimensional 0-1 knapsack, satellite photo planning and cellular network optimisation. We validate our work by improving a large number of results on difficult benchmarks.
Abstract FR:
La recherche tabou est une méthode approchée réputée performante pour de nombreux problèmes combinatoires. Nous cherchons dans cette thèse à renforcer cette méta-heuristique pour la résolution efficace de problèmes de grande taille. Pour ce faire, nous exploitons trois voies complémentaires et intimement liées. Premièrement, nous proposons d'enrichir la caractéristique locale de tabou par combinaison avec des méthodes à caractère global, telles que la programmation linéaire et l'énumération exhaustive. Deuxièmement, nous accordons un rôle très important aux contraintes lors de la conception des éléments tels que le voisinage, l'heuristique de mouvement et même le mécanisme général d'exploration de l'espace de recherche. Troisièmement, nous introduisons une mise en œuvre efficace de l'algorithme dans le cadre d'une formulation binaire des problèmes. Nous expérimentons cette approche sur trois problèmes difficiles, de taille et de complexité croissantes : le sac à dos multidimensionnel en 0-1, la planification de photos satellite et l'optimisation des réseaux cellulaires. Nous validons l'ensemble de nos travaux en améliorant un grand nombre de résultats sur des benchmarks juges difficiles.