|
 
|
[Cot16] d-extensibles, d-bloqueurs et d-transversaux de problèmes d’optimisation combinatoire
Mémoire de Thèse :Mots clés: Optimisation dans les graphes, ensembles stables, optimisation bi-niveau.
Résumé:
Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.
Les d-extensibles de stables optimaux sont des ensembles de sommets d’un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l’aide de sommets qui n’appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d’un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d’un d-extensible et étudions quelques classes d’arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.
Les d-bloqueurs de stables sont des ensembles de sommets d’un graphe G tels que, si on retire les sommets d’un d-bloqueur, le cardinal maximal d’un stable du graphe induit par les sommets restants est inférieur d’au moins d au cardinal maximal d’un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d’arbres particulière.
Soit Πun problème d’optimisation sur un ensemble d’éléments fini. Un d-transversal de Πest un ensembles d’éléments tel que l’intersection entre le d-transversal et toute solution optimale au problème Πest de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux
BibTeX
| @phdthesis { | |||
| Cot16, | |||
| title | = | "{d-extensibles, d-bloqueurs et d-transversaux de problèmes d’optimisation combinatoire}", | |
| author | = | "G. Cotté", | |
| year | = | 2016, | |
| address | = | "{CEDRIC Laboratory, Paris, France}", | |
| } |
