Sujet de stage de recherche M2 informatique

  • titre: graphes d'intervalles pour les problèmes de placement
  • Responsable: Arnaud Pêcher (maître de conférences habilité à diriger des recherches)
  • Téléphone : 05 40 00 21 77
  • e-mail: pecher@labri.fr
  • Équipe: Combinatoire et Algorithmique
  • Thème : Graphes et applications
  • Equipe INRIA: RealOpt

Présentation du sujet :

La modélisation par des graphes par Feketete et Shepers (1997) du problème du placement de formes orthogonales dans un conteneur a permis de faire un saut quantitatif quant à la taille des problèmes traités. En effet, en représentant les solutions par des graphes, de nombreuses symmétries (i.e. des solutions identiques) sont éliminées et les bonnes propriétés algorithmiques des graphes mis en jeu, des graphes d'intervalle, sont la clef pour la conception de l'algorithme de Fekete/Shepers.

Cette modélisation est illustrée dans la figure ci-dessous, 5 boites sont placées dans le grand carré. A ce placement est associé deux graphes d'intervalle: G1 (en haut) et G2 (en bas). Les sommets de G1 (resp. G2) correspondent aux boites; deux sommets sont adjacents si et seulement si la projection des deux boites sur l'axe vertical (resp. horizontal) s'intersecte

Le travail demandé consiste à:

  1. comprendre et implémenter l'algorithme de Fekete et Schepers (1)
  2. rechercher des algorithmes alternatifs reposant sur des modèles plus évolués de représentations des graphes d'intervalles (ex. PQ arbres)
  3. rechercher des formulations type programmation mathématique

Ce travail s'inscrit dans le cadre des activités de l'équipe-projet INRIA RealOpt.

Bibliographie et urls :

  1. S.P. Fekete, J.Schepers, J.van der Veen. An exact algorithm for higher-dimensional orthogonal packing Operations Research, Vol. 55, No. 3, 2007, pp. 569-587.
  2. equipe INRIA RealOpt: http://realopt.math.cnrs.fr(approve sites)