Le 21/11/2016 par fouilhoux :

Sujet du stage

De nombreux problèmes d'Optimisation Combinatoire en Recherche Opérationnelle possèdent des structures intéressantes pour les techniques de décomposition en programmation linéaires en nombres entiers (PLNE): problèmes de coloration de graphe, de tournées de véhicules, de la planification de démarrage d'unités de production,...

Ces techniques de décomposition construisent des PLNE possédant un nombre exponentiel de variables entières. L'approche classique pour résoudre ces techniques est d'utiliser un algorithme de génération de colonnes pour résoudre la relaxation linéaire du problème maître, puis d'utiliser cet algorithme à chaque noeud d'un arbre de branchement, ce que l'on nomme les algorithmes de Branch-and-Price.

Dans une telle approche algorithmique, les aspects combinatoires du problème maître sont bien souvent mis de côté par rapport à la difficulté technique de résolution du problème auxiliaire de génération de colonnes. Des travaux expérimentaux récents mènent à reconsidérer cette vision: la génération de colonnes ainsi pratiquée produit en effet des variables utiles pour la résolution de la relaxation mais inutiles pour la résolution en nombres entiers du problème.

Ce sujet s'intègre dans la continuité de travaux de l'équipe RO sur une technique algorithmique permettant d'utiliser de manière générique des inégalités valides pour le problème maître dans le cadre d'une génération de colonnes.

L'objectif de ce stage est double: approfondir les aspects théoriques de cette approche et la mettre en oeuvre sur des problèmes classiques d'optimisation combinatoire.

Objectifs du stage

Le double aspect théorique et pratique de ce sujet permet une grande diversité de déroulements du stage: il peut ainsi se concentrer plus ou moins sur des aspects théoriques ou programmation en fonction du profil d'étudiants. Il est même envisageable de focaliser ce sujet uniquement sur des aspects théorique ou sur des aspects programmation.

Voici quelques exemples de sujets possibles:

• Généralisation des techniques de prises en comptes d'inégalités valides dans le problème maître de problèmes dit de ``set-partionning'': applications au problème de tournées de véhicules (VRP).
  En s'intéressant de manière générique aux décompositions où le problème maître est réduit à un problème de partition, nous généraliserons les inégalités issues du polyèdre des partitions pour les intégrer dans le problème auxiliaire du VRP qui est le problème du plus court chemin contraint.
• Etude polyédrale du problème de couvertures d'un graphe par des stables: application au problème de coloration de graphes.
  Dans cet aspect du sujet, nous nous intéressons au polyèdre de couvertures d'un graphe par des stables qui est la structure combinatoire du problème maître de la décomposition du problème de coloration de graphe. Une étude préalable de ce polyèdre laisse penser que les facettes de ce polyèdre ont toute une structure unique particulière. Cette étude théorique mène à une mise en oeuvre naturelle de ces inégalités au travers d'une génération de colonnes simples.

Pour plus d'informations:

http://androide.lip6.fr/?q=node/226