Séminaire en format hybride au local 4488 du GERAD ou Zoom.
Given a graph G with a set of pairs of terminals (si,ti), i=1,…,K, a cost on each edge of G, and two fixed integers L≥2 and k≥2, the k-edge-disjoint L-hop-connected paths problem is to find a minimum cost subgraph such that between every pair of terminals si and ti there are at least k edge-disjoint paths of length at most L. This problem has applications in the design of telecommunication networks.
We will discuss some variants of this problem from a polyhedral point of view. We give integer programming formulations, and introduce several classes of valid inequalities. We also discuss separation routines for these inequalities. Using this we propose a Branch-and-Cut algorithm for the problem when L=2,3 and k=2.
Moreover, we will show that when L = 3, k ≥ 2, and K=1, the linear relaxation of the associated polytope is integral. As a consequence, we obtain a polynomial time cutting plane algorithm for the problem in this case.
