Abstract FR:

Dans le domaine de l'optimisation combinatoire, il est necessaire de developper des methodes de resolution permettant de reduire le temps d'execution souvent prohibitif. Afin d'obtenir des methodes plus efficaces pour le probleme du sac a dos en variables bivalentes, nous proposons d'une part l'utilisation conjointe de la programmation dynamique et de l'enumeration implicite et d'autre part d'utiliser la puissance de calcul offerte par les machines paralleles. Dans la premiere partie, la methode branch-and-bound est abordee. Nous mettons en evidence le fait que la separation est un aspect aussi essentiel que la strategie de parcours. Apres avoir presente les ameliorations de la programmation dynamique et les methodes hybrides existantes qui permettent de reduire le nombre des etats a considerer, nous proposons dans la seconde partie une nouvelle methode hybride qui surpasse ces dernieres. Elle consiste a reduire le nombre d'etapes necessaires a la resolution. Dans la troisieme partie, nous mettons en evidence la necessite d'obtenir une methode robuste. Pour cela nous proposons une nouvelle methode mixte, basee sur la cooperation de la technique branch-and-bound et de la programmation dynamique qui se revele tres efficace pour toutes les instances de problemes. Dans la quatrieme partie, nous avons etudie la parallelisation de l'algorithme branch-and-bound en strategie de parcours en meilleur d'abord. La granularite de l'application etant tres fine, notre but a ete de reduire le nombre de communications necessaires. Nous avons considere deux types d'implantation : par le paradigme maitre-esclaves et par la circulation d'un jeton dans un anneau. Pour la version a file de priorite globale, nous avons propose une methode qui permet de grossir efficacement le grain de l'application. Une extention de ce principe a ete realisee pour des files de priorite locales en utilisant une strategie de repartition de charge basee sur la requete.