Optimisation combinatoire 1
concepts fondamentaux
Traité IC2, série Informatique et Systèmes d'Information

Cet ouvrage est le premier d'une série intitulée "Optimisation combinatoire". Ses sujets traitent des thématiques fondamentales de l'optimisation combinatoire. L'ouvrage est divisé en trois parties : éléments de la théorie de la complexité, méthodes classiques de résolution exacte des problèmes, et notions et méthodes de la programmation mathématique. La première partie présente les fondements de la théorie de la complexité déterministe et probabiliste. La deuxième partie présente les méthodes par séparation et évaluation et la programmation dynamique. La troisième partie est centrée sur la programmation mathématique, le coeur de l'optimisation combinatoire et de la recherche opérationnelle. Dans ce volume, un grand nombre de modèles linéaires pour un aussi grand nombre de problèmes d'optimisation combinatoire est d'abord exposé et commenté.

SUR LA COMPLEXITÉ DES PROBLÈMES D'OPTIMISATION COMBINATOIRE. Concepts de base de l'algorithmique et de la théorie de la complexité -V.-Th Paschos. Complexité Probabiliste -J. Barbay. QUELQUES MÉTHODES CLASSIQUES DE RÉSOLUTION. Méthodes arborescentes par séparation et évaluation (branch and bound) - I. Charon, O. Hudry. Programmation dynamique -B. Escoffier, O. Spanjaard. ÉLÉMENTS DE LA PROGRAMMATION MATHÉMATIQUE. Modélisation de problèmes d'optimisation combinatoire à l'aide de la programmation linéaire mixte entière -F. Della Croce. Un tour d'horizon de quelques méthodes de programmation linéaire -P. Tolla. Optimisation quadratique en variables 0-1 -A. Billionnet. Génération de colonnes en programmation linéaire en nombres entiers -I. Loiseau, A. Ceselli, N. Maculan, M. Salani. Approches polyédrales -A.-R. Mahjoub. Programmation par contraintes -C. Le Pape. Index.