Séminaire Cedric Joncour

Jeudi 22 Mars 2012 (16h00)

Cedric Joncour, LMAH.

Titre : Modélisation et résolution du problème de placement.

Résumé : Le problème de placement sur deux dimensions consiste à décider s’il existe un rangement d’objets rectangulaires dans une boîte donnée, sans rotation des objets. Ce problème est connu pour être NP-difficile. En particulier, il possède de nombreuses symétries de solutions difficiles à caractériser. Dans cet exposé, nous nous intéresserons aux différentes approches de résolution exactes pour ce problème combinatoire. Ainsi, je commencerai par présenter les différentes formulations mathématiques du problème. Puis, je vous exposerai de nouvelles modélisations du problème, utilisant des matrices et des arbres labellisés. Ces modèles permettent d'obtenir des algorithmes combinatoires efficaces face aux formulations mathématiques.