Titre                       :    Algorithmes pour la gestion des contraintes en optimisation combinatoire
Équipe                   :    Dolphin (CRIStALUMR CNRS 9189, Inria Lille-Nord Europe)
Encadrants            :    Arnaud Liefooghe et Bilel Derbel
Contact                  :    arnaud.liefooghe [at] univ-lille1.fr



1. Contexte et problématique

Un problème d'optimisation combinatoire a pour but de trouver une solution optimisant un ou plusieurs objectifs et répondant à un ensemble de contraintes. Par exemple, le problème du sac-à-dos classique vise à sélectionner un sous-ensemble d'éléments dans une collection de n éléments en maximisant une ou plusieurs fonctions profit et satisfaisant une ou plusieurs contraintes de ressource (la capacité du sac), basée sur des fonctions poids. Une solution est alors spécifiée par une chaîne binaire de taille n, de sorte que chaque variable indique si l'élément correspondant est inclus dans le sous-ensemble des éléments sélectionnés (le sac) ou non.

Contrairement aux approches classiques de la programmation mathématique, les métaheuristiques sont des méthodes de haut niveau à usage général qui sont relativement simples à développer tout étant en mesure de fournir des solutions efficaces en pratique à des problèmes d'optimisation combinatoire difficiles et de grande taille. Lors de la conception de métaheuristiques pour ces problèmes optimisation combinatoire, il existe essentiellement trois catégories générales pour la gestion des contraintes : (1) pénaliser les solutions irréalisables, (2) réparer les solutions irréalisables, ou (3) concevoir une représentation et des opérateurs spécifiques pour le problème à résoudre. Il est bien entendu que la performance d'une technique de gestion de contraintes est fortement liée aux caractéristiques du problème à résoudre. Cependant, savoir quelle approche donnera de meilleures résultats reste une question ouverte.


2. Travail à réaliser

Dans ce projet, nous nous proposons d'analyser l'impact des caractéristiques du problème sur la performance des techniques de gestion des contraintes. En particulier, nous allons établir une corrélation entre la nature des fonctions objectif (profit) et des fonctions contrainte (poids) sur la performance d'une métaheuristique, en utilisant différentes techniques de gestion des contraintes (pénalisation et/ou réparation).

Les objectifs du projet sont les suivants :
1. Concevoir de nouveaux problèmes test, en particulier des problèmes d'optimisation combinatoire mono- et multi-objectif binaires, comme le sac-à-dos.
2. Concevoir une métaheuristique polyvalente, capable d'utiliser toute fonction de pénalité et/ou de réparation.
3. Mener une étude expérimentale de l'impact de la gestion des contraintes sur la performance de la métaheuristique.
4. Fournir des recommandations pour la fonction de pénalité et/ou de réparation à utiliser en fonction des caractéristiques du problème test.

En fonction des compétences et/ou des préférences du candidat, le projet prendra une orientation "technique" ou "recherche". Par ailleurs, des développements complémentaires peuvent inclure des techniques alternatives de gestion des contraintes et différents problèmes d'optimisation combinatoire. 

Le projet pourra donner lieu à une poursuite en stage, en fonction de la motivation du candidat et des résultats obtenus.


3. Partitionnement des tâches

— 20% analyse de la littérature, compréhension des concepts existants
 40% conception et expérimentation de l'algorithme proposé et de ses différentes variantes
 30% comparaison avec d'autres approches
 10% analyse et synthèse des résultats obtenus


4. Le candidat idéal

Il/elle devra
 être motivé(e) et intéressé(e) par l'algorithmique en général
 maitriser un langage de programmation orienté-objet


5. Bibliographie

[1] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer, 2004
[2] Z. Michalewicz and D. B. Fogel. How to solve it - modern heuristics. Springer, 2004
[3] E-G. Talbi. Metaheuristics: from design to implementation. Wiley, 2009
[4] E. Mezura-Montes. Constraint-handling in evolutionary optimization. Springer, 2009
[5] K. Deb. Multi-objective optimization using evolutionary algorithms. Wiley, 2001