Robust Discrete Optimization Under Ellipsoidal Uncertainty

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.Cette thèse traite la version robuste des problèmes linéaires à variables binaires avec un ensemble d'incertitude corrélé. Puisque ce problème est NP-difficile, une approche heuristique intitulée DFW et basée sur l'algorithme de Frank-Wolfe est proposée. Dans cette approche, notre intérêt porte sur les solutions des approximations linéaires que l’algorithme exhibe au long des itérations pendant la relaxation de l’espace des contraintes dans l’enveloppe convexe. Pour les problèmes de petites tailles, la méthode est capable de fournir la solution optimale fournie par CPLEX, après quelques centaines d’itérations. De plus, contrairement à la méthode exacte, notre approche s’applique à des problèmes de grandes tailles également. Les résultats numériques ont été appliqués au plus court chemin robuste. Un autre objectif de cette thèse est de proposer une relaxation semi-définie positive (SDP) pour le plus court chemin robuste qui fournit une borne inférieure pour valider des approches telles que l’algorithme DFW. Ceci permet d’éviter la comparaison entre la solution heuristique et celle proposée par la méthode exacte. Le problème relaxé est le résultant d’une bidualisation du problème. Puis le problème relaxé est résolu en utilisant une version creuse d'une méthode de décomposition dans un espace produit. Cette méthode de validation est adaptée aux problèmes de grande taille. Les expériences numériques montrent que l’écart entre les solutions proposées par les méthodes exacte et heuristique est relativement petit. Finalement, une autre adaptation de l'algorithme de Frank-Wolfe a été réalisé pour le problème du k-médiane. Elle consiste d'abord à relaxer les contraintes de binarité et à utiliser l'algorithme de Frank-Wolfe pour le problème convexe. Ensuite, elle utilise une technique d'arrondissement pour la moyenne des solutions intermédiaires de l'algorithme afin de donner une solution heuristique qui est une solution qui satisfait les contraintes de clustering. Les résultats montrent que cette approche donne la solution optimale dans la plupart des cas, et qu'elle donne des solutions proches de l'optimal lorsqu'elles ne le sont pas