Méthode hybride pour la résolution des problèmes de programmation linéaire en nombres entiers

Abstract

Les problèmes d'optimisation linéaire en nombres entiers permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Dans ce travail, les différentes méthodes exactes qui résolvent ces problèmes sont explicitement citées. En particulier, la méthode de coupes, la méthode de Branch-and-Bound, la programmation dynamique et la méthode de support à variables bornées. Les méthodes approchées sont aussi citées. Ce mémoire s'intéresse à la mise en oeuvre d'une méthode de résolution hybride pour obtenir des solutions de bonne qualité en un temps raisonnable. On combine la méthode de support à variables bornées avec une heuristique. Lors de processus de résolution, à chaque étape, un problème relaxé est résolu par la méthode de support et sa solution optimale est soumise à une procédure d'arrondissement judicieusement choisie. le concept le B-optimalité permet d'indiquer la qualité d'une solution approchée obtenue par cette heuristique.