Soutenance de thèse de Quentin DELMEE (équipe SLP)

Quentin Delmée, doctorant au sein de l’équipe SLP soutiendra sa thèse intitulée « Résolution Exacte de problèmes de localisation de services bi-objectif en variables mixtes »

vendredi 19 octobre 2018 à 10h00, dans l’amphi du bâtiment 34 sur le site de la Faculté des Sciences et Techniques

Jury : Xavier Gandibleux (directeur de thèse), Anthony Przybylski (co-encadrant), Laetitia Jourdan (Rapporteur, Université de Lille), Saïd Hanafi (Rapporteur, Université de Valenciennes et du Hainaut Cambrésis), André Rossi (examinateur, Université Paris Dauphine), Audrey Cerqueus (examinateur, Mines Saint-Etienne)

Résumé :
Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret.
Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif.
Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons.

Mots-clés : Optimisation bi-objectif, Problème de localisation de services, Programmation linéaire en variables mixtes, Branch and Bound

********

Abstract:
The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restrictedto the discrete case. We consider first  the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods.

Keywords: Bi-objective optimization, Facility Location Problems, Mixed Integer Linear Programming, Branch and Bound