Show simple item record

Conception de réseaux fiables avec fortes contraintes de sommet-connexité : Étude polyédrale et Algorithmes

dc.contributor.advisorMahjoub, Ali Ridha
dc.contributor.advisorBen Charrada, Faouzi
dc.contributor.authorMahjoub, Meriem*
dc.date.accessioned2018-06-19T12:00:34Z
dc.date.available2018-06-19T12:00:34Z
dc.date.issued2017-12-13
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17852
dc.description.abstractfrDans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB.fr
dc.language.isoen
dc.subjectConception de réseauxfr
dc.subjectPolytopefr
dc.subjectFacettefr
dc.subjectSéparationfr
dc.subjectAlgorithme de Coupes et Branchementsfr
dc.subjectAlgorithme de Génération de Colonnes et Branchementsfr
dc.subjectK-Node-Connected graphen
dc.subjectK-Node-Disjoint hop-Constrained pathsen
dc.subjectSurvivable Networken
dc.subjectPolytopeen
dc.subjectFacetsen
dc.subjectSeparationen
dc.subjectBranch-And-Cuten
dc.subjectBranch-And-Cut-And-Priceen
dc.subject.ddc004
dc.titleThe Survivable Network Design Problems with High Node-Connectivity Constraints : Polyhedra and Algorithmsen
dc.titleConception de réseaux fiables avec fortes contraintes de sommet-connexité : Étude polyédrale et Algorithmesfr
dc.typeThèse
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.contributor.editoruniversityotherUniversité de Tunis El Manar
dc.description.abstractenGiven a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.en
dc.identifier.theseid2017PSLED046
dc.subject.ddclabelInformatique générale
hal.person.labIds*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record