Chifaa DAHIK : "Robust Discrete Optimization Under Ellipsoidal Uncertainty"

Abstract : This thesis addresses the Robust counterpart of binary linear problems with ellipsoidal uncertainty sets. Since this problem is hard, a heuristic approach, based on Frank- Wolfe’s algorithm named Discrete Frank-Wolf (DFW), has been proposed. In this approach, we are interested in the optimum of the linear approximation that the algorithm computes at each iteration when relaxing the constraint set in its convex hull. For small dimensional instances, our method is able to provide the same optimal integer solution as an exact method provided by CPLEX, after no more than a few hundred iterations. Moreover, as opposed to the exact method, DFW Algorithm applies to large scale problems as well. The numerical results are applied on the robust shortest path problem (RSPP). Another aim of this thesis is to propose a Semi-Definite Programming (SDP) relaxation for the RSPP that provides a lower bound to validate approaches such as DFW Algorithm. This is to avoid comparing the heuristic solution with the optimal one given by the exact method. The relaxed problem results from a bidualization of the problem. Then the relaxed problem is solved using a sparse version of a decomposition in a product space method. This validation method is suitable for large size problems. The numerical experiments show that the gap between the solutions obtained with the relaxed and the heuristic approaches is relatively small. Finally, another adaptation of FW, named MFW Algorithm, has been proposed for the k-median problem. It consists first in relaxing the binarity constraints and using the Frank- Wolfe Algorithm for the convex problem. Then, it uses a rounding technique for the mean of the intermediate steps of the algorithm to give a heuristic solution that is a feasible clustering solution. Results show that this approach gives the optimal solution in most of the cases, and that it gives close-to-optimal solutions when they are not optimal

Jury Composition :

M. Jean-Marc NICOD Professeur Université Bourgogne Franche-Comté - PhD Director
M. Landy RABEHASAINA Maître de conférences Université de Franche-Comté - PhD Co-director
Mme Zeina AL MASRY Maître de conférences ENSMM - PhD Co-Director
Mme Andréa Cynthia SANTOS Professeure Université Le Havre - Reporter
M. Imed KACEM Professeur Université de Lorraine - Repoorter
M. Clément DOMBRY Professeur Université de Franche-Comté - Reviewer
M. Stéphane CHRETIEN Professeur Université de Lyon 2 -- Reviewer
M. Kim Thang NGUYEN Professeur Université de Paris Saclay - Reviewer

Localization : Amphithéâtre Jules Haag - ENSMM, 26 Rue de l'Epitaphe - 25000 Besançon