Abstract FR:

Dans plusieurs cas, et a cause de facteurs exterieurs, on est amene a faire face a une situation inattendue pouvant etre formulee par un probleme d'optimisation combinatoire. Dans ce cas nous devons prendre une decision rapide et trouver une solution en moins de temps possible. Cette situation est en general une modification d'un des parametres de la situation habituelle ou, en terme d'optimisation combinatoire, une perturbation d'une partie des donnees de l'instance du probleme initial. Partant de ce constat, un premier aspect de ce travail est le developpement de methodes adaptatives c'est-a-dire des methodes permettant de resoudre des situations inattendues ou des instances de problemes avec des donnees perturbees en tirant profit de la resolution de l'instance initiale. Nous avons developpe ces methodes adaptatives pour un probleme particulier d'optimisation combinatoire qui est le probleme du knapsack. Malgre la simplicite de sa formulation, le probleme du knapsack possede de nombreuses applications pratiques et intervient dans plusieurs cas comme un sous-probleme permettant la resolution d'autres problemes. Ceci fait de lui un modele theorique particulierement interessant qui a ete tres etudie. Un deuxieme aspect de ce travail est l'etude de methodes exactes pour le probleme du knapsack et deux de ses variantes : le probleme du setup knapsack et du knapsack sharing. Ces deux problemes sont tres proches par leur formulation. Dans les deux cas il s'agit d'un probleme du knapsack ou les objets sont divises en familles ou classes disjointes avec ajout de contraintes logiques (probleme du setup knapsack) ou changement de la fonction objective sous forme max-min (probleme du knapsack sharing).