Optimisation combinatoire

La matière développée ici est une synthèse de différents enseignements donnés à l'Ecole Nationale des Ponts et Chaussées puis à l'Université Scientifique et Medicale de Grenoble et à l'Ecole Nationale Supérieure d'Informa tique et de Mathématiques appliquées de Grenoble au cours des quinze dernières années. C'est dire qu'il s'agit d'abord d'un ouvrage didactique dans lequel on fait largement appel à l'intuition du lecteur (grâce en particulier à l'utilisation de nombreux exemples). Si les théories sont décrites de manière rigoureuse, ce n'est jamais dans un but purement esthétique mais en référence à leurs retombées algorithmiques. Les algorithmes sont d'ail leurs présentés de manière parfaitement claire.

Après un rappel des principaux concepts et résultats du volume "Graphes et programmation linéaire", cet ouvrage commence par une présentation de la théorie de la complexité des algorithmes. La suite est consacrée à l'étude des problèmes de cheminement, d'ordonnancement et de flot. Puis on décrit les méthodes de solution des problèmes d'optimisation combinatoire réputés "difficiles": procédures par séparation et évaluation ("branch and bound"), méthodes de coupes, programmation dynamique et enfin méthodes approximatives ou heuristiques. On peut considérer qu'il s'agit d'autant de monographies qui peuvent être lues indépendamment et constituent des manuels de référence dans ces domaines. L'ouvrage pourra être utilisé comme tel par les étudiants en mathématiques appliquées et en informatique ou les élèves des grandes écoles d'ingénieurs. Il pourra également être consulté par tous ceux qui, ayant achevé leurs études depuis quelques années, souhaitent s'initier à des disciplines qui n'étaient pas enseignées au moment de leur formation initiale.

Table

• Chapitre 1 Introduction
• Chapitre 2 De l'éfficacité des algorithmes à la complexité des problèmes
• Chapitre 3 Problèmes de cheminement : algorithmes de plus court chemin ; ordonnancement
• Chapitre 4 Problème du flot maximum ; théorème de la coupe minimum et applications
• Chapitre 5 Flots de coût minimum ; algorithme primal-dual ; problème de transport
• Chapitre 6 Les méthodes par séparation et évaluation ; énumération implicité ; relaxation lagrangienne
• Chapitre 7 Méthodes de coupes : étude polyédrale des problèmes d'optimisation combinatoire
• Chapitre 8 Programmation dynamique
• Chapitre 9 Méthodes approximatives
• Annexes