Aller au menu Aller au contenu
UGA
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire

Qu'est-ce que l'Optimisation Combinatoire ?

Résoudre des problèmes de mathématiques discrètes et concevoir des algorithmes efficaces

Mis à jour le 8 avril 2015
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentTélécharger au format PDFEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

L'Optimisation Combinatoire consiste à trouver un "meilleur" choix parmi un ensemble fini (souvent très grand) de possibilités. Nous explorons et exploitons les propriétés structurelles des problèmes ("bonnes" caractérisations, décompositions, etc) qui permettent de concevoir des algorithmes efficaces (exacts ou approchés) ou alors montrent que de tels algorithmes n'existent pas.

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.


A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentTélécharger au format PDFEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

Rédigé par Benoit Serraillier

mise à jour le 8 avril 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Communauté Université Grenoble Alpes
×
Afin d'améliorer la qualité de ce site et le service rendu à l'utilisateur, nous utilisons des cookies de mesure d’audience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies à cette fin. Pour en savoir plus