Les problèmes d'optimisation combinatoire se rencontrent partout dans l'industrie, notamment dans les domaines du transport (planification), des télécommunications (conception et exploitation de réseaux), de la micro-informatique (conception de circuits intégrés, ordonnancement), de la logistique (ordonnancement, empaquetage) etc.. Ce sont des problèmes très difficiles et, dans un cadre opérationnel, cette difficulté se traduit par un arbitrage permanent entre les moyens mis en oeuvre (puissance de calcul et espace mémoire) et les enjeux de l'optimisation : selon les contraintes de temps (décisions en temps réel vs. simulation), les contraintes d'optimalité (résolution d'un système de contraintes impératives vs. optimisation qualitative) ou encore la maîtrise du risque (préférence d'une solution dont la performance est garantie théoriquement à une solution empiriquement meilleure), on s'orientera vers telle ou telle approche de résolution.
Cet enseignement présente les principales approches de résolution de ces problèmes, ainsi que les outils mathématiques et informatiques dont on dispose aujourd'hui pour concevoir des solutions adaptées en réponse à une problématique précise. Un soin particulier sera donné à présenter les justifications d'utilisation d'une approche en fonction d'un contexte : si l'on cherche une solution exacte, il faudra utiliser une méthode arborescente ; si l'on cherche une solution rapide, on préfèrera une méthode heuristique ou méta-heuristique ; si l'on veut une garantie absolue de performance, on rejettera les approches méta-heuristiques, etc..
Un intérêt particulier sera porté sur les approches dites à garantie de performance : le degré de difficulté des problèmes d'optimisation combinatoire fait qu'on ne peut toujours se permettre de les résoudre à l'optimum ; quitte à fournir des solutions seulement approchées, les algorithmes à garantie de performance se donnent la double exigence d'une efficacité en temps (les algorithmes sont rapides) et en performance (on sait situer la solution fournie par rapport à la meilleure, éventuellement à la pire, solution). À travers cette étude, c'est l'analyse plus que la conception même des algorithmes qui sera mise en avant.
Le but de cette première partie est de faire prendre conscience de la difficulté de résolution des problèmes d'optimisation combinatoire : en passant d'un espace réel à un espace discret, on perd tous les outils du continu. Pour mesurer à la fois la difficulté d'un problème et la qualité d'un algorithme, il faut intégrer la notion de complexité.
Cette deuxième partie présente brièvement les différents choix algorithmiques qui sont offerts pour résoudre un problème d'optimisation combinatoire. On insistera notamment sur les atouts et faiblesses des approches qui seront présentées, en termes de complexité et de qualité des solutions fournies.
L'enjeu de cette dernière partie est d'approfondir l'étude des algorithmes à garantie de performance ; elle est aussi l'occasion de mettre en oeuvre les techniques présentées au cours de la partie précédente dans le cadre de l'approximation. On s'attachera à toujours illustrer les classes d'approximation par l'analyse d'un algorithme pour le voyageur de commerce, afin de mieux cerner la spécificité de chacun des outils utilisés.