Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses

ZHAO Jinhua


Maximum Bounded Rooted-Tree Problem : Algorithms and Polyhedra

Lundi 19 juin - 14h 00 - Amphi 1 du pôle commun ISIMA/Polytech

This PhD research work focuses on the Maximum Bounded Rooted-Tree (MBrT) problem from a polyhedral-combinatorics viewpoint. This NP-hard combinatorial-optimization problem quite recently arose in under-provisioned content delivery networks. After proving that the MBrT problem is NP-hard, we provide polynomial-time algorithms to solve it on trees, cycles, and more generally on cactus graphs. We then consider two underlying polytopes, an extended one with both edge- and node-indexed variables and a natural one with only edge-indexed variables. For each polytope, we study its dimension, strengthen an initial formulation by introducing new families of facet-defining inequalities, and provide complete characterizations on non-trivial classes of graphs. These theoretical results are implemented into branch-and-cut frameworks enhanced with a matheuristic using the optimization software IBM ILOG CPLEX. Intensive computational experiments prove that the strengthened formulations considerably increase the size of the instances that can be optimally solved in a timely manner.

Membres du jury :
· M. Mohamed DIDI-BIHA, Professeur, LMNO, Université de Caen-Normandie, Rapporteur
· Mme Sourour ELLOUMI, Professeur, ENSTA Paris-Tech, Rapporteur
· M. A. Ridha MAHJOUB, Professeur, LAMSADE, Université Paris-Dauphine, Rapporteur
· Mme Fatiha BENDALI-MAILFERT, Maître de Conférences HDR, LIMOS, Université Clermont-Auvergne, Examinateur
· M. Hervé KERIVIN, Maître de Conférences, LIMOS, Université Clermont-Auvergne, Directeur de thèse
· M. Philippe MAHEY, Professeur, LIMOS, Université Clermont-Auvergne, Directeur de thèse.