Optimisation combinatoire
B. Korte et J. Vygen
Springer
2009
664 pages
79.9 €
L’optimisation combinatoire consiste à optimiser une certaine fonction sur un ensemble discret. Rien de plus simple a priori, il suffit d’énumérer tous les éléments de l’ensemble fini en question et de choisir le ou les élément(s) optimum. L’ennui, bien sûr, est que ce nombre d’éléments peut être « énorme ». Prenons par exemple le problème du voyageur de commerce. Celui-ci doit visiter n villes différentes reliées par un certain
nombre de routes. Le problème est de minimiser la distance parcourue. Si chaque couple de villes est relié par une route, cela fait n! possibilités. L’algorithme naïf qui consiste à dresser la liste de tous les trajets possibles est très vite impraticable.
Un grand nombre de problèmes sont de cette sorte ; il s’agit des problèmes NP-complets. Dans ce cas, il existe souvent des méthodes approchées. Les Allemands Bernhard Korte et Jens Vygen sont tous deux des spécialistes reconnus dans le milieu de l’optimisation combinatoire. Leur dernier ouvrage, Optimisation combinatoire
– Théorie et algorithmes, traite des problèmes NP-complets de manière théorique. En particulier, il contient un très bon chapitre sur la NPcomplétude, et tous les algorithmes sont prouvés. Il traite aussi les questions pratiques, les algorithmes étant décrits dans un pseudo langage facile à transcrire. Au final, un excellent livre de référence sur la question, de niveau mastère et doctorat.
