Presentation on YouTube.

Given a graph G with a set of pairs of terminals \((s_i,t_i),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 \(s_i\) and \(t_i\) 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.

Biography: A. Ridha Mahjoub is Professor Emeritus at Université Paris-Dauphine, Paris, France. He is also member of the LAMSADE laboratory, CNRS. Previous positions include Professor Classe Exceptionnelle of Operations Research and Combinatorial Optimization at University Paris-Dauphine from 2007 to 2022, full professor at the University of Brest, France, from 1991 to 1998 and the University of Clermont-Ferrand, France, from 1998 to 2007. Professor Mahjoub holds an undergraduate degree in Mathematics from University of Tunis, Tunisia and a Ph.D. and a Thèse d’Etat in Operations Research and Combinatorial Optimization from the University of Grenoble, France. His research areas include the theory and applications of polyhedral approaches for modeling, analysing and solving large NP-hard combinatorial optimization problems, mixed integer programming as well as complexity and graph theory. A part of his research has recently focused on the design of cutting plane algorithms for network design problems. Professor Mahjoub is author and co-author of several papers that have appeared in leading journals such as Mathematical Programming, Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, Discrete Mathematics, Discrete Applied Mathematics, Discrete Optimization, Informs Journal on Computing, Operations Research letters and Networks. He served as co-director of the Mathematics and Computer Science Department at Université Paris-Dauphine between 2008 and 2013. Professor Mahjoub edited and co-edited books and several special issues of journals. He currently serves as Editor-in-Chief of the international journal RAIRO-Operations Research.