• Langue : Français
• Discipline : Sciences mathématiques. Informatique
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 01/01/2010

Résumé en langue originale

Nous décrivons de nouvelles modélisations et des approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Les structures « simples » des problèmes de bin-packing et de sac à dos font que ces problèmes NP-difficiles font partie des plus étudiés dans la littérature de recherche opérationnelle. Ils ont été notamment à la base de nombreuses contributions concernant les algorithmes d'approximation ou la programmation en nombres entiers. Il apparaît clairement que les méthodes développés pour ces problèmes ont des répercussions pour de nombreuses applications en optimisation combinatoire, ce qui justifie la très abondante littérature dont ils font l'objet. Au cours de notre travail, nous avons mobilisé des résultats provenant de plusieurs disciplines au sein de la communauté optimisation à l'aide de modèles originaux.- Nos travaux utilisent en effet des résultats de programmation mathématique, programmation par contraintes, méta-heuristiques, programmation dynamique et de théorie des graphes. Ces méthodes sont utilisées dans des méthodes collaboratives qui reposent très fortement sur nos nouveaux modèles. Nous avons tout d'abord travaillé sur des méthodes de décompositions et des méthodes méta-heuristiques basées sur des stratégies dite d'oscillation. Ces techniques ont été validées sur des problèmes de packing avec différents types de conflits. Une autre famille de contributions concerne les fonctions dites dual-réalisables, qui permettent d'obtenir des évaluations par défaut rapides pour plusieurs problèmes de packing, et d'améliorer des coupes en programmation en nombres entiers. Nous proposons aussi des modèles originaux pour des problèmes de placement en deux dimensions.- Ces modèles donnent lieu à des techniques hybridant techniques de programmation par contraintes et recherche opérationnelle. Toutes nos contributions sont validées de manière théorique (classes de complexité, preuves de dominance) et pratique (expérimentation et comparaison avec les meilleures méthodes de la littérature). Elles donnent lieu à de nombreuses perspectives pour la résolution de problèmes de packing et pour la mise en place de méthodes collaboratives.