Digiteo - Recherche en sciences et technologies de l'information

Optimisation problems can be stated as follows: given a set of variables taking values in some given domains (either discrete or continuous) and a set of constraints, find an assignment of values to variables that minimises some objective functions. Optimisation is tremendously useful in real life applications such as routing, scheduling, computational biology, etc. People working in the area of optimisation either focuses 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, probability theory, stochastic processes, graph theory, and artificial intelligence...

A non-exhaustive list of topics where DIGITEO teams are involved: Algorithms and Complexity Algorithmic questions are mostly focused on complexity issues (is the problem NP-Hard?) and on approximability issues i.e. design of polynomial algorithms with performance guarantees.

• Efficient algorithms for computing Nash equilibriums.
• Randomized algorithms.
• New approximation approaches e.g. Fixed Parameter Tractability algorithms.

Combinatorial Optimisation and Mathematical Programming
Applied mathematicians have heavily contributed to the efficiency of mixed integer programming solvers. Over the last two decades the introduction of efficient cuts, that remove regions of the search space that do not contain optimal solutions, has made it possible to solve large problems.

• Semidefinite Programming.
• Interior Point Methods.
• Column Generation and Polyhedral Methods.
• Convex Optimisation.

Stochastic Optimisation
Stochastic Combinatorial Optimization for solving new problems where a subset of parameters is randomly distributed and the variables are integer. The challenge of this recent area in optimisation is to solve real life problems where uncertainty is embedded in the original problem.

• Chance Constraint Programming.
• Multistage stochastic combinatorial optimisation problems.
• Stochastic Gradient Methods.
• Stochastic Evolutionary Algorithms.

Constraint 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.

• Hybridisation.
• Integration with other optimisation approaches.

Evolutionary Computation
Evolutionary Computation 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.

• Machine learning.
• Evolutionary computation.

Graph Theory
Graph theory is a basic theory and important tool in computer science. Classical fundamental problems of cycles and colourings in graph theory and also many related problems are studied. Digiteo Partners research work is very often related to the following themes:

• Hamiltonicity, Colouring.
• Dominating cycle, Connectivity.
• Partition, Decomposition.
• Applications to sensor networks.

Chair and Optimisation Seminars
A senior Chair is funded by DIGITEO until 2012. Professor Pierre Hansen from HEC Montreal and GERAD is working on different topics of Combinatorial Optimisation. A semiannual workshop called OPTIMEO is organised alternatively by DIGITEO partners.