Abstract FR:

À l'origine destinées à la résolution de programmes linéaires continus, les méthodes intérieures ont trouvé un champ d'applications beaucoup plus large incluant aussi bien les programmes quadratiques que les problèmes d'optimisation en nombres entiers et plus récemment encore, les problèmes de programmation semi-définie. Les méthodes intérieures représentent une bonne alternative à la méthode du simplexe, particulièrement pour des problèmes de grande taille dont la matrice des contraintes possède une structure appropriée. Par conséquent, plusieurs méthodes de type branch-and-bound utilisant des techniques de points intérieurs ont été développées pour la programmation entière depuis une dizaine d'années. Cette thèse est consacrée a l'élaboration d'une méthode hybride performante pour la résolution approchée de programmes linéaires en nombres entiers, reposant sur une combinaison originale d'un algorithme de points intérieurs et d'ajout de coupes avec une métaheuristique. Elle débute par une recherche arborescente qui met en jeu une méthode intérieure et deux types de coupes (économiques et valides), engendrant un ensemble diversifié de solutions entières réalisables. Ces solutions permettent de construire la population initiale d'une métaheuristique de type recomposition de chemins (path relinking), qui est une méthode de combinaison de couples de solutions. Ce concept de combinaison permet d'élargir le champ d'exploration du domaine des solutions en travaillant sur la base non pas d'une solution unique mais d'une population de solutions. Notre méthode est validée par des expériences numériques effectuées sur des instances de programmes linéaires en variables 0-1 (sac à dos multidimensionnel, problème général d'affectation).