Abstract FR:

Dans cette these, on propose des methodes de decomposition suivies d'algorithmes appropries pour resoudre quelques problemes combinatoires. Le chapitre 0 introduit les problemes de stable, de recouvrement et de partition dans un hypergraphe. Le chapitre 1 montre une premiere decomposition; l'algorithme qui en est issu est specialise au probleme de recouvrement. Le chapitre 2 propose une decomposition de benders du probleme du stable de poids maximum dans un hypergraphe. Dans le chapitre 3, on decrit une heuristique basee sur une decomposition lagrangienne du probleme d'affectation generalisee. Le chapitre 4 est consacre a une reduction d'un probleme de transport special dans lequel certaines destinations sont groupees et expriment une demande commune, a un probleme de flot entier a arcs homologues