Résumé: Dans cette thèse, on propose des méthodes de décomposition suivies d'algorithmes appropries pour résoudre quelques problèmes combinatoires. Le chapitre 0 introduit les problèmes de stable, de recouvrement et de partition dans un hypergraphe. Le chapitre 1 montre une première décomposition; l'algorithme qui en est issu est spécialise au problème de recouvrement. Le chapitre 2 propose une décomposition de benders du problème du stable de poids maximum dans un hypergraphe. Dans le chapitre 3, on décrit une heuristique basée sur une décomposition lagrangienne du problème d'affectation généralisée. Le chapitre 4 est consacré a une réduction d'un problème de transport spécial dans lequel certaines destinations sont groupées et expriment une demande commune, a un problème de flot entier a arcs homologues

Clermont-Ferrand:
Langue: Français
Collation: 99 p. ill. ;30 cm
Diplôme: Doctorat
Etablissement de soutenance: Clermont-Ferrand, Clermont-Ferrand
Spécialité: Informatique
Thème Informatique

Note: Bibliogr.pp.90-99