Cette thèse s'inscrit dans le cadre d'une étude polyhédrale des problèmes de conception de réseaux fiables avec forte connexité. En particulier, nous considérons les problèmes dits du sous-graphe k-arête-connexe et de conception de réseau k-arête-connexe avec contrainte de borne lorsque k _>3. Dans un 1er temps, nous étudions le problème du sous-graphe k-arête-connexe. Etant donné un graphe non orienté et valué G = (V, E) et un entier positif k, le problème du sous-graphe k-arête-connexe consiste à déterminer un sous-graphe de G de poids minimum telle qu'il existe k chaînes arête-disjointes entre chaque paire de sommets de V. Nous discutons du polytope associé à ce problème lorsque k _>3. Nous introduisons une nouvelle famille d'inégalités valides pour le polytope et présentons plusieurs familles d'inégalités valides. Pour chaque famille d'inégalités, nous étudions les conditions sous lesquelles ces inégalités définissent des facettes. Nous discutons aussi du problème de séparation associé à chaque famille d'inégalités ainsi que d'opérations de réduction de graphes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et donnons des résultats expérimentaux. Ensuite, nous étudions le problème de conception de réseaux k-arête-connexe avec contrainte de borne. Soient G = (V, E) un graphe valué non orienté, un ensemble de demandes D _C V x V et deux entiers positifs k et L. Le problème de conception de réseaux k-arête-connexe avec contrainte de borne consiste à déterminer un sous-graphe de G de poids minimum telle qu'entre chaque paire de sommets {s, t} E D, il existe k chaînes arête-disjointes de longueur au plus L. Nous étudions ce problème dans le cas où k _>2 et L E {2, 3}. Nous examinons la structure du polytope associé et montrons que, lorsque I D I = 1, ce polytope est complètement décrit par les inégalités dites de st-coupe et de L-chemin-coupe avec les inégalités triviales. Ce résultat généralise ceux de Huygens et al. [75] pour k = 2, L E {2, 3} et Dahl et al. [35] pour k _>2, L = 2. Enfin, nous nous intéressons au problème de conception de réseau k-arête-connexe avec contrainte de borne lorsque k _>2, L E {2, 3} et I D I _> 2. Le problème est NP-difficile dans ce cas. Nous introduisons quatre nouvelles formulations du problème sous la forme de programmes linéaires en nombres entiers. Celles-ci sont basées sur la transformation du graphe G en graphes orientés appropriés. Nous discutons du polytope associé à chaque formulation et introduisons plusieurs familles d'inégalités valides. Pour chacune d'elles, nous décrivons des conditions pour que ces inégalités définissent des facettes. En utilisant ces résultats, nous développons des algorithmes de coupes et branchements et de coupes, génération de colonnes et branchements pour le problème. Nous donnons des résultats expérimentaux et menons une étude comparative entre les différentes formulations.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00724580 |
| Date | 07 December 2009 |
| Creators | Diarrassouba, Ibrahima |
| Publisher | Université Blaise Pascal - Clermont-Ferrand II |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds