Given a graph G= (N,E), two integers k,L, and a subset of pairs of nodes D, we want to determine the minimum cost subgraph in G having at least k edge-disjoint paths of at most L hops between all the pairs in D. Several particular cases are considered. For each of them, we realize a polyhedral study of the associated polytope.
The aim is to devise an efficient Branch and Cut algorithm based on these results in order to solve real size instances of that problem.
Supervisor:
Prof. Martine Labbé (ULB, Belgium).