Informatique Informatique et mathématiques discrètes (IMD)
Un problème d'optimisation combinatoire est caractérisé par un espace de solutions très grand mais que l'on peut décrire de manière compacte, comme l'ensemble des couplages, des st-chemins, des arbres couvrants ou des cycles hamiltoniens d'un graphe ou encore l'ensemble des permutations de n entiers. Une fonction objectif permet d'évaluer la qualité de chacune des solutions de l'espace de recherche. Résoudre un problème d'optimisation combinatoire c'est trouver une solution qui minimise ou maximise la fonction objectif. De nombreux problèmes aussi bien pratiques que théoriques se formulent de cette manière.

L'objectif du cours est de présenter quelques idées fondamentales qui permettent de concevoir des algorithmes efficaces pour résoudre de façon exacte ou avec une garantie de performance des problèmes d'optimisation combinatoire.

On insistera en particulier sur les notions suivantes :

L'approche polyédrale consiste à représenter chaque solution de l'espace de recherche par son vecteur caractéristique et à étudier l'enveloppe convexe de ces vecteurs. Si celle-ci peut-être décrite de façon compacte (par exemple, par un nombre d'inégalités polynomial dans la taille de l'entrée du problème) alors la programmation linéaire permet d'obtenir un algorithme de résolution efficace.
Une telle description vient souvent avec un résultat de type min-max qui permet de définir l'optimum du problème de minimisation que l'on cherche à résoudre comme l'optimum d'un autre problème de maximisation (ou l'inverse). La dualité de la programmation linéaire fournit un tel résultat. Elle est à la base de la conception de nombreux algorithmes efficaces (polynomial) de résolution exacte ou approchée via la méthode primale-duale.
Même lorsqu'une représentation polyédrale compacte n'est pas disponible, en particulier pour les problèmes NP-difficiles, l'approximation de l'enveloppe convexe par des inégalités linéaires, appelées coupes, permet de fournir des bornes cruciales pour la résolution pratique des problèmes NP-difficiles par des méthodes de type séparation-évaluation-coupes (branch-and-cut). Nous illustrerons chacune de ces notions ou approches sur différents problèmes classiques : couplage, flot et coupes, arborescence, TSP, indépendant commun à deux matroïdes, arbre et réseau de Steiner, problème de localisation, etc.