navigation

Changer la langue :

Langue / language

Rechercher

 

Optimisation

First published : Friday 1 August 2008 by Sophie Pales

Optimisations problems can be stated as follows: given a set of variables taking values in some given domains (either discrete or finite) and a set of constraints, find an assignment of values to variables that minimises some objectives functions.

Optimisation is tremendously useful in real life applications such as routing, scheduling, computational biology, etc. People working in the area of optimisation either focus on building efficient models of real life problems or on specific techniques that improve the performance of solvers. Optimisation is a multidisciplinary research area that uses techniques from algorithmic, applied mathematics, artificial intelligence.

 

  • Algorithmic questions are mostly focused on complexity issues (is the problem NPHard?) and on approximability issues (How good are solutions that can be found inpolynomial time?).

Hot topic: Efficient algorithms for computing Nash equilibriums

 

  • Applied mathematicians have heavily contributed to the efficiency of mixed integer programming solvers. Over the last 15 years the introduction of efficient cuts that remove regions of the search space that do not contain optimal solutions allow to solve large problems.

Hot topic: Semi-definite Programming

 

  • One of the key ideas of Constraint programming is that constraints can be used "actively" to reduce the computational effort required to solve combinatorial problems. Constraints are thus not only used to test the validity of a solution, as in conventional programming languages, but also in an active mode to remove values from the domains, deduce new constraints, and detect inconsistencies. Constraint programming solvers have shown to be extremely efficient on some combinatorial problems such as scheduling.

Hot topic: Hybridisation and integration with other optimisation technologies

 

  • Graph Theory. Properties of graphs are useful to derive efficient algorithms for various fields of optimisation..

Hot topic: Graph Colouring

 

  • Evolutionary Computation and stochastic optimisation are adapted to global optimisation, to multi-criteria optimisation, and to ill-posed optimisation problems, such as those involved in machine learning, data mining, identification, optimal policies, and inverse problems.

Hot topic: Relationship between machine learning and evolutionary computation.