• The two-edge connected Hop-con...

Treffer: The two-edge connected Hop-constrained Network Design Problem : Valid inequalities and branch-and-cut

Title:
The two-edge connected Hop-constrained Network Design Problem : Valid inequalities and branch-and-cut
Authors:
HUYGENS, David, LABBE, Martine, RIDHA MAHJOUB, A, PESNEAU, Pierre
Source:
Multicommodity flows and network designNetworks (New York, NY). 49(1):116-133
Publisher Information:
New York, NY: John Wiley & Sons, 2007.
Publication Year:
2007
Physical Description:
print, 34 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Connectivité graphe, Graph connectivity, Conectividad grafo, Graphe complet, Complete graph, Grafo completo, Graphe pondéré, Weighted graph, Grafo pondero, Méthode séparation et coupe, Branch and cut method, Método branch and cut, Polytope, Politope, Problème NP difficile, NP hard problem, Problema NP duro, Programmation en nombres entiers, Integer programming, Programación entera, Sous graphe, Subgraph, Subgrafo, Système réparti, Distributed system, Sistema repartido, Temps polynomial, Polynomial time, Tiempo polinomial, Arête disjointe, Disjoint edge, Arista disyuntiva, NP-hardness, branch-and-cut, edge connectivity, facets, hop-constraints, network design, valid inequalities
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Département d'Informatique, Université Libre de Bruxelles, Boulevard du Triomphe, CP 210/01, 1050 Bruxelles, Belgium
LIMOS, CNRS, UMR 6158, Université Blaise Pascal, Clermont-Ferrand II, Complexe Scientifique des Cézeaux, 63177 Aubière, France
IAG/POMS, Université Catholique de Louvain, Place des Doyens, 1, 1348 Louvain-la-Neuve, Belgium
ISSN:
0028-3045
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18405631
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18405631
Database:
PASCAL Archive

Weitere Informationen

This article deals with the Two-edge connected Hop-constrained Network Design Problem (or THNDP for short). Given a weighted graph G = (N, E), an integer L ≥ 2, and a subset of pairs of nodes D, the problem consists of finding the minimum cost subgraph in G containing at least two edge-disjoint paths of at most L hops between all the pairs in D. First, we show that the THNDP is strongly NP-hard even when the demands in D are rooted at some node s and the costs are unitary. However, if the graph is complete, we prove that the problem in this case can be solved in polynomial time. We give an integer programming formulation of the problem in the space of the design variables when L = 2,3. Then we study the associated polytope. In particular, we consider the case where all the pairs of nodes of D are rooted at a node s. We give several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also derive separation routines for these inequalities. We finally develop a branch-and-cut algorithm based on these results and discuss some computational results for L = 2,3.