Faithin Omaha eBook Collection

Download or read book Problèmes d'optimisation combinatoire sous contraintes written by Lionel Lobjois and published by . This book was released on 1999 with total page 208 pages. Available in PDF, EPUB and Kindle. Book excerpt: Nous étudions dans cette thèse deux voies pour résoudre plus efficacement les problèmes d'optimisation combinatoire exprimés dans le cadre génétique VCSP (Valued Constraint Satisfaction Problem), extension du cadre CSP (Constraint Satisfaction Problem) pour l'optimisation. La première voie concerne la recherche de nouvelles méthodes globalement plus performantes par la coopération entre méthodes complètes et méthodes incomplètes. Nous proposons en particulier une nouvelle méthode hybride dédiée à la résolution de VCSP en contexte interruptible et la comparons aux recherches locales standards. La seconde voie concerne la recherche d'outil d'aide à la décison permettant d'utiliser une méthode adaptée à chaque situation, c'est-à-dire adaptée à l'instance à résoudre et au temps imparti à la résolution de cette instance. Nous proposons tout d'abord une adaptation de la méthode proposée par Knuth en 1975 afin d'estimer le temps de résolution des méthodes complètes de type séparation et évaluation. Nous envisageons ensuite une série d'application potentielles pour cet estimateur. Nous proposons notamment la méthode SPP (algorithm Selection by Performance Prediction) capable de sélectionner, instance par instance, l'algorithme le plus performant parmi une base d'algorithmes complets. Nous terminons ce mémoire par quelques voies permettant d'étendre cette méthode à une construction automatique d'algorithmes complets "optimisés" pour chaque instance.