Aller au menu Aller au contenu
UGA
Combinatorial Optimisation
Laboratory of Grenoble for sciences of conception, optimisation and production
Combinatorial Optimisation

What is Combinatorial Optimisation ?

Solve problems from Discrete Mathematics and design efficient algorithms

Updated on March 13, 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

Combinatorial Optimization consists in finding a "best" choice among a finite (but usually very large) set of possibilities. We find and use structural properties of the problems we consider ("good" caracterizations, decompositions, ...) in order to design efficient algorithms (exact or approximate) or to show that such algorithms do not exist.

Combinatorics, discrete mathematics, graph theory: three different names for very close fields. They correspond to a branch of Mathematics that has appeared in the 20th century to address the needs of various disciplines:
  • computer science,
  • scheduling of large-scale production,
  • management of military operations (see the origins of the name operations research)
  • economy
  • ...

A large number of branches have later appeared, and those we study can be called Combinatorial Optimization.

Combinatorial Optimization consists in finding the best solution among a finite (but typically very large) number of choices. It is a branch of Mathematical Programming, which covers all methods used to determine the optimium of a function under various constraints. The purpose is to minimize a function over a finite, but usually very large set, whose mathematical properties are not easy to characterize. Investigating such characterizations, and the optimization algorithms using them, is the base of the work of our team. We use our expertise in this domain to investigate new problems (purely theoretical ones or some having industrial applications), to analyze them and extract fundamental properties that could be used to solve them or show that their resolution is hard. We develop theoretical tools enabling us to solve a wide variety of problems with adequate methods (exact, heuristics, approximation algorithms, ...) that can be generic or tailor-made.

These results and the related activities - seminars, international projects, lectures and teaching, exchange programs for young researchers - make Grenoble an attractive center in this field and more generally in Discrete Mathematics.


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

Written by Louis Esperet

Date of update March 13, 2015

Communauté Université Grenoble Alpes
×
To improve the quality of this site and the service rendered to the user, we use cookies audience measurement. By continuing your visit to this site, you agree to our use of cookies for this purpose. More