Sujet de projet long - N7 3ème année

  • titre: problèmes de placement: mission gcut13
  • 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.

Attach:OPP.png Δ

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.

Attach:FSimage.png Δ

Nous avons développé deux nouveaux algorithmes en Java qui exploitent cette modélisation. Ces deux algorithmes sont significativement plus rapides que celui de Fekete & Schepers, sur les jeux de tests standards. Il existe une instance classique (appelée gcut13) qui n'a jamais été résolue entièrement, et pour laquelle nous avons réussi à améliorer la borne inférieure. Votre mission, si vous l'acceptez, est de tout mettre en oeuvre pour résoudre gcut13:

  1. implémenter le schéma d'énumération de Fekete & Chepers. En effet, nos deux algorithmes prennent seulement en charge la phase de décision: étant donné un ensemble d'objets pré-sélectionnés, nos algorithmes déterminent s'il existe un placement valide pour ces objets. Pour tester notre code sur les jeux de tests standards, nous avons implémenté un schéma d'énumération (Branch-and-Bound) classique pour la pré-sélection des objets, bien moins efficace que celui de Fekete & Schepers.
  2. parallélisation de l'algorithme de présélection des items, pour tirer pleinement avantage des multi-coeurs: le gain en performance sera immédiat et crucial pour pouvoir espérer résoudre gcut13.
  3. conception d'heuristiques efficaces basées sur ces algorithmes exacts
  4. paramétrage fin adapté à gcut13
  5. visualisation en cours de construction du placement: une propriété remarquable de nos algorithmes est que tout au long du déroulement, le placement (partiel) des objets est connu. En ajoutant une fonction de visualisation au cours des calculs (et non à la fin), cela permettrait pour gcut13 de visualiser les placements que nos algorithmes peinent à résoudre.

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