Sujet de TER M1 informatique

  • titre: démonstrateur pour les problèmes de placment
  • Responsable: Arnaud Pêcher (professeur)
  • Téléphone : 05 61 55 74 27
  • e-mail: arnaud.pecher@irit.fr
  • Équipe: Algorithmes Parallèles et Optimisation
  • Equipe INRIA: RealOpt

Présentation du sujet :

Le problème consistant à sélectionner un ensemble d'objets rectangulaires qui peuvent être placés sans chevauchement dans un conteneur rectangulaire, de manière à minimiser l'espace inoccupé est un problème classique en recherche opérationnelle. La figure ci-dessous est une illustration de ce problème: les objets 1,2,3,4,5 et 6 admettent un tel placement, cependant l'objet 7 ne peut être mis avec eux.

La modélisation par des graphes par Feketete et Shepers (1997) de ce problème 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.

Nous avons développé deux nouveaux algorithmes qui exploitent cette modélisation.

Le travail demandé consiste à développer un démonstrateur en Java, qui comprendra deux modes:

  1. mode normal: l'utilisateur définit les données du problème (ie les objets rectangulaires et la taille du conteneur) - nos algorithmes fournissent alors une solution optimale (ou bien la meilleur solution trouvée en un temps donné) sous la forme de la liste des objets sélectionnés et des coordonnées pour réaliser le placement. Le programme doit alors dessiner la solution.
  2. mode pédagogique (à destination des enfants): l'utilisateur sélectionne une instance du problème et essaie de trouver une solution en déplaçant les objets à la souris; le programme indique si une meilleure solution est possible.

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. logiciel AlgoKP: https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/SoftwareAlgoKP