Combinatorial Optimisation
Laboratory of Grenoble for sciences of conception, optimisation and production

# 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 documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

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 documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

Date of update March 13, 2015

## Responsable

Dir. de Recherche CNRS
Responsable OC
46, avenue Félix Viallet - 38031 Grenoble Cedex 1 - France
Tél +33 (0)4 76 57 50 71 - Fax +33 (0)4 76 57 46 95