M�thodes de R�solution Hybrides Pour Les Probl�mes de Type Knapsack

Dans cette thse, nous nous intressons aux problmes du knapsack multidimensionnel choix multiple. Ils interviennent essentiellement en tlcommunication. Nous proposons de nouvelles mthodes hybrides de rsolution exacte et approche. Dans un premier temps, nous proposons des mthodes heuristiques en se basant sur les techniques de gnration de colonnes et d'arrondi. Ensuite, nous abordons une mthode de recherche locale, dite mthode de branchement local, o des contraintes linaires sont introduites pour intensifier et diversifier la recherche. Cette mthode est ensuite hybride avec la gnration de colonnes et une technique d'arrondi. Concernant la rsolution exacte, nous nous basons sur une mthode de "Branch and cut". Nous commenons par proposer de nouvelles contraintes valides pour le problme. Ensuite, nous les associons des contraintes de couverture locales et globales dans un schma numratif. Les approches heuristiques et l'algorithme exact que nous proposons sont compars d'autres heuristiques de la littrature et au Solveur de programmes linaires Cplex.