Le Probl me Du Sac DOS Multidimensionnel : Heuristiques multi-étapes et méthode coopérative de résolution

Le problme du sac dos plusieurs contraintes est un problme classique de l'optimisation appartenant la classe des problmes NP-difficiles. On le retrouve notamment sous la forme de sous-problme de nombreux problmes d'optimisation combinatoire. Les mthodes classiques de rsolution exacte telles que la programmation dynamique ou le branch-and-bound ont t traites abondamment dans la littrature. Elles prsentent nanmoins des faiblesses si elles sont utilises telles quelles, d'o l'ide de faire cooprer ces mthodes en tirant profit de leurs spcificits afin de proposer soit des mthodes heuristiques performantes, soit des mthodes exactes plus efficaces. Les approches heuristiques que nous proposons sont compares d'autres heuristiques de la littrature. Notre mthode cooprative est, quant elle, compare un algorithme de branch-and-bound. L'ensemble de ces tests numriques ont t mens pour diverses instances plus ou moins difficiles de la littrature ainsi que sur des instances engendres alatoirement.