Qu'est-ce que l'Optimisation Combinatoire ?

Combinatoire, mathématiques discrètes, théorie des graphes : trois termes synonymes, ou presque. Ils représentent une branche des mathématiques née au vingtième siècle grâce aux besoins de divers domaines :

• l'informatique
• l'organisation de la production à grande échelle
• la gestion des opérations militaires (voir les origines du terme recherche opérationnelle)
• l'économie
• ...

Un grand nombre de ramifications se sont par la suite développées,   celles que nous traitons peuvent être regroupées sous le terme d' Optimisation Combinatoire.

L'Optimisation Combinatoire consiste à trouver la meilleure solution parmi un nombre fini (mais souvent très grand) de choix. C'est une branche de la « Programmation Mathématique » qui recouvre les méthodes qui servent à déterminer l'optimum d'une fonction sous des contraintes données. Il s'agit donc de minimiser une fonction sur un ensemble fini, mais éventuellement très grand, et dont les propriétés mathématiques ne sont pas facilement caractérisables. La recherche de ces caractérisations, et des algorithmes d'optimisation qui les utilisent, constitue l'essentiel du travail de l'équipe. Nous nous basons sur notre expertise pour cerner de nouveaux problèmes, théoriques ou appliqués, et les analyser pour en extraire les propriétés fondamentales qui permettront de les résoudre ou de montrer que leur résolution est difficile. De plus, nous utilisons et développons des outils théoriques qui permettent de traiter ces problèmes avec des méthodes appropriées (exactes, heuristiques, algorithmes d'approximation, etc), qui peuvent être « ad hoc » ou « génériques ».

Grâce aux résultats obtenus et aux activités qui en découlent - séminaires, projets internationaux, exposés et cours, accueil d'un grand nombre de jeunes chercheurs - Grenoble est un centre attractif du domaine et plus généralement des mathématiques discrètes.