" Combinatoire " désigne la discipline des mathématiques concernée par les structures " discrètes " ou " finies ". Citons quelques branches de cette discipline : la théorie des graphes, la combinatoire énumérative, les problèmes de dénombrement, la combinatoire polyédrale, l'optimisation combinatoire, etc. Les frontières entre les branches ne sont pas hermétiques, les différentes branches expriment plutôt des orientations méthodologiques différentes.
L'" optimisation ", ou " programmation mathématique " (Mathematical Programming) sont des termes utilisés pour recouvrir toutes les méthodes qui servent à déterminer l'optimum d'une fonction avec (ou sans) contraintes. Cette fonction modélise le choix optimal. On optimise déjà à l'école, quand on apprend comment déterminer l'optimum (minimum ou maximum) d'une fonction différentiable. Les ingénieurs, les économistes..., la nature, font souvent des choix optimaux (ou quasi-optimaux), d'où l'importance de l'optimisation dans les sciences, qu'elles soient techniques, mathématiques, physiques, informatiques, économiques, naturelles, etc.
L' " Optimisation combinatoire " consiste à trouver le meilleur entre un nombre fini de choix. Autrement dit, minimiser une fonction, avec contraintes, sur un ensemble fini. Quand le nombre de choix est exponentiel (par rapport à la taille du problème), mais que les choix et les contraintes sont bien structurées, des méthodes mathématiques doivent et peuvent intervenir, comme dans le cas " continu ", pour permettre de trouver la solution en temps polynomial (par rapport à la taille du problème). Le travail de l'équipe consiste à développer des algorithmes polynomiaux et des théorèmes sur des structures discrètes qui permettent de résoudre ces problèmes.
Telle que nous l'entendons, l'Optimisation combinatoire se situe au carrefour de la Théorie des graphes, de la Programmation mathématique, de l'Informatique théorique (algorithmique et théorie de la complexité) et de la Recherche opérationnelle. (Historiquement et aussi dans notre travail, la théorie de la complexité d'algorithmes et l'optimisation combinatoire se doivent beaucoup l'une à l'autre.) Nous avons des résultats qui appartiennent à un ou plusieurs de ces domaines et sont publiés dans les revues suivantes : Journal of Combinatorial Theory, Journal of Graph Theory, Combinatorica, Mathematical Programming, Discrete Mathematics, SIAM Journal on Discrete Mathematics, SIAM Journal on Computing, Journal of Algorithms.
Ce sont les meilleures revues internationales de notre domaine. Nous sommes aussi, souvent acteurs de ces mêmes revues, par notre travail de " referee ".
Les mots clefs de notre recherche sont : (multi-)flots dans les réseaux, couplages, matroïdes, théorèmes de bonne caractérisation (théorèmes minimax), polyèdres, optimisation linéaire (ou convexe), dualité, cônes polyédraux, algorithmes polynomiaux, problèmes NP-complets etc.. Nos outils principaux sont la programmation mathématique, l'algèbre linéaire, la complexité des problèmes (algorithmes polynomiaux et résultats de NP-complétude), la théorie des graphes. Nos sujets de recherche sont à la fois alimentés par des applications, et aussi la logique, (l'esthétique) et le développement intérieur de la théorie. Voici une présentation plus détaillée des objets combinatoires que nous étudions.