Note publique d'information : Dans 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.
Note publique d'information : Given 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.
paprika.idref.fr
data.idref.fr
Documentation
