Anzeige
Erschienen in:
16.01.2018
k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut
Erschienen in: Annals of Telecommunications | Ausgabe 1-2/2018
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a graph with weights on the edges, a set of origin and destination pairs of nodes, and two integers L ≥ 2 and k ≥ 2, the k-node-disjoint hop-constrained network design problem is to find a minimum weight subgraph of G such that between every origin and destination there exist at least k node-disjoint paths of length at most L. In this paper, we consider this problem from a polyhedral point of view. We propose an integer linear programming formulation for the problem for L ∈{2,3} and arbitrary k, and investigate the associated polytope. We introduce new valid inequalities for the problem for L ∈{2,3,4}, and give necessary and sufficient conditions for these inequalities to be facet defining. We also devise separation algorithms for these inequalities. Using these results, we propose a branch-and-cut algorithm for solving the problem for both L = 3 and L = 4 along with some computational results.