Le problème du sac à dos à plusieurs contraintes est un problème classique de l'optimisation appartenant à la classe des problèmes NP-difficiles. On le retrouve notamment sous la forme de sous-problème de nombreux problèmes d'optimisation combinatoire. Les méthodes classiques de résolution exacte telles que la programmation dynamique ou le branch-and-bound ont été traitées abondamment dans la littérature. Elles présentent n'eanmoins des faiblesses si elles sont utilisées telles quelles, d'où l'idée de faire coopérer ces méthodes en tirant profit de leurs spécificités afin de proposer soit des méthodes heuristiques performantes, soit des méthodes exactes plus efficaces. Les approches heuristiques que nous proposons sont comparées à d'autres heuristiques de la littérature. Notre méthode coopérative est, quant à elle, comparée à un algorithme de branchand- bound. L'ensemble de ces tests numériques ont été menés pour diverses instances plus ou moins difficiles de la littérature ainsi que sur des instances engendrées aléatoirement. Enfin, nous proposons deux techniques pour engendrer des problèmes difficiles. Ces dernières sont basées sur des problèmes en contraintes égalités et sur l'analyse de la transformée en Z du sac à dos.

Dans cette thèse, nous nous intéressons à la résolution exacte de programmes linéaires en variables binaires. L'ensemble de nos travaux s'articule autour de l'étude de Resolution search (Chvátal (1997)) pour la résolution du problème du sac à dos multidimensionnel en 0-1. Dans un premier temps, nous proposons un algorithme d'énumération implicite centré sur une analyse des coûts réduits à l'optimum de la relaxation continue ainsi que sur une décomposition de l'espace de recherche en hyperplans. Nous proposons une stratégie de branchement originale visant à élaguer au plus tôt l'arbre de recherche. Cette stratégie est efficace pour résoudre des instances jugées difficiles mais rend l'algorithme dépendant de la connaissance d'une bonne solution de départ. Dans un deuxième temps, nous proposons une méthode de résolution plus autonome combinant Resolution search avec une énumération implicite inspirée du premier algorithme. Cette coopération permet d'obtenir rapidement de bonnes solutions et prouve les optimums d'instances de plus grande taille. Finalement, nous présentons une application de Resolution Search à la résolution d'un problème de planification dans le domaine des télécommunications.

Les problèmes d'optimisation en variables 0-1 mixtes permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Cette thèse s'intéresse à la mise en oeuvre de méthodes de résolution hybrides pour obtenir des solutions de bonne qualité en des temps raisonnables pour ces problèmes. L'ensemble des algorithmes présentés dans cette thèse est testé sur le problème du sac-à-dos multidimensionnel. Il consiste à maximiser une fonction linéaire en respectant un ensemble de contraintes linéaires. Après une présentation de quelques concepts fondamentaux utilisés en recherche opérationnelle pour résoudre les problèmes d'optimisation, nous présentons dans le premier chapitre différents problèmes de la famille du sac-à-dos. Nous abordons dans le second chapitre un ensemble de méthodes efficaces existantes pour résoudre le problème du sac-à-dos multidimensionnel. Nous proposons dans le chapitre 3 une première méthode hybride qui combine la programmation dynamique et la recherche tabou au sein d'un processus dit d'intensification globale. Des concepts de réduction sont également intégrés dans la programmation dynamique de manière à essayer de réduire la taille du problème. La seconde approche décrite dans le chapitre 4 combine la recherche dispersée avec des éléments de la recherche tabou et des chemins reliants pour affiner la recherche. Une étude expérimentale est menée pour mesurer l'impact de différents composants de l'algorithme. Nous terminons dans le chapitre 5 par une méthode utilisant conjointement la relaxation en continu et la relaxation en nombres entiers mixtes pour résoudre efficacement les problèmes en variables 0-1. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes. La dernière approche permet d'améliorer quelques meilleures valeurs connues sur des instances existantes du problème du sac-à-dos multidimensionnel.