en fr Composition of polyhedra and their relation to some combinatorial optimization problems Composition de polyèdres associés aux problèmes doptimisation combinatoire Report as inadecuate




en fr Composition of polyhedra and their relation to some combinatorial optimization problems Composition de polyèdres associés aux problèmes doptimisation combinatoire - Download this document for free, or read online. Document in PDF available to download.

1 IMAG - Institut d-Informatique et de Mathématiques Appliquées de Grenoble

Résumé : Le polyèdre associé à un problème d-optimisation combinatoire est l-enveloppe convexe des vecteurs d-incidence des solutions réalisables de ce problème. De nombreux problèmes d-optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d-inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L-objet principal de cette thèse est l-étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d-unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes composition par identification de sous-graphes de deux graphes donnés, adjonction d-une nouvelle arête sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

Mots-clés : Optimisation combinatoire Polyèdre Programmation linéaire Programmation dynamique Méthode projection Problème commis voyageur Théorie graphe Polytope des stables Graphe parfait





Author: Ahmed Hadjar -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents