Accueil > Manifestations > Thèses et HDR > Thèses > Audrey Cerqueus

Audrey Cerqueus

Directeur de thèse

Xavier Gandibleux
Frédéric Saubion
Anthony Przybylski

Résumé

Dans ce travail, nous nous intéressons à la résolution de problèmes d’optimisation combinatoire multi-objectif. Ces problèmes ont suscité un intérêt important au cours des dernières décennies. Afin de résoudre ces problèmes, particulièrement difficiles, de manière exacte et efficace, les algorithmes sont le plus souvent spécifiques au problème traité. Dans cette thèse, nous revenons sur l’approche dite de branch-and-bound et nous en proposons une extension pour obtenir un branch-and-cut, dans un contexte bi-objectif. Les problèmes de sac-à-dos sont utilisés comme support pour ces travaux. Trois axes principaux sont considérés : la définition de nouveaux ensembles bornants, l’élaboration d’une stratégie de branchement dynamique et la génération d’inégalités valides. Les ensembles bornants définis sont basés sur la relaxation surrogate, utilisant un ensemble de multiplicateurs. Des algorithmes sont élaborés, à partir de l’étude des différents multiplicateurs, afin de calculer efficacement les ensembles bornants surrogate. La stratégie de branchement dynamique émerge de la comparaison de différentes stratégies de branchement statiques, issues de la littérature. Elle fait appel à une méthode d’apprentissage par renforcement. Enfin, des inégalités de couverture sont générées et introduites, tout au long de la résolution, dans le but de l’accélérer. Ces différents apports sont validés expérimentalement et l’algorithme de branch-and-cut obtenu présente des résultats encourageants.

Mots clés :

optimisation combinatoire multi-objectif, branch-and-cut, stratégie de branchement, relaxation surrogate, problème de sac-à-dos bi-objectif.

Composition du jury :

  • Arnaud Fréville, Professeur, Université de Valenciennes et du Hainaut-Cambrésis, Rapporteur
  • Kathrin Klamroth, Professeur, Bergische Universität Wuppertal, Rapporteuse
  • Thomas Stuetzle, Professeur, Université Libre de Bruxelles, Rapporteur
  • Daniel Vanderpooten, Professeur, Université de Paris-Dauphine, Examinateur
  • Xavier Gandibleux, Professeur, Université de Nantes, Directeur de thèse
  • Frédéric Saubion, Professeur, Université d’Angers, Co-encadrant
  • Anthony Przybylski, Maître de conférences, Université de Nantes, Co-encadrant

Abstract :

In this work, we are interested in solving multi-objective combinatorial optimization problems. These problems have received a large interest in the past decades. In order to solve exactly and efficiently these problems, which are particularly difficult, the designed algorithms are often specific to a given problem. In this thesis, we focus on the branch-and-bound method and propose an extension by a branch-and-cut method, in bi-objective context. Knapsack problems are the case study of this work. Three main axis are considered : the definition of new upper bound sets, the elaboration of a dynamic branching strategy and the generation of valid inequalities. The defined upper bound sets are based on the surrogate relaxation, using several multipliers. Based on the analysis of the different multipliers, algorithms are designed to compute efficiently these surrogate upper bound sets. The dynamic branching strategy arises from the comparison of different static branching strategies from the literature. It uses reinforcement learning methods. Finally, cover inequalities are generated and introduced, all along the solving process, in order to improve it. Those different contributions are experimentally validated and the obtained branch-and-cut algorithm presents encouraging results.

Key Words :

multi-objective combinatorial optimization, branch-and-cut, branching strategies, surrogate relaxation, bi-objectif knapsack problem.

Dernière modification : vendredi 13 novembre 2015