Optimisation, Structure & Algorithms

The research conducted in the Optimization, Structure & Algorithms group is mainly about optimization. The group has a long tradition of studying combinatorial (i.e., discrete) problems, but recent developments include continuous aspects such as derivative-free optimization. Optimization problems are ubiquitous: minimizing some costs, or maximizing a profit, are recurring tasks of policy makers, manufacturers, and individuals. That is why algorithms with good performances (in terms of quality of the output and running time) can have a major impact on the society. Indeed, many present challenges can be cast as optimization problems : reducing pollution, saving energy, increasing the welfare of a population, etc. However, most optimization problems are complex and they involve different sources of intractability. Optimization, Structure & Algorithms group contributes to the understanding and efficient resolution of optimization problems at different levels of abstraction: from theoretical analysis to concrete applications.

The main topics of the group are Optimization (mainly combinatorial optimization, but
also continuous optimization), Structure (determine and study the parameters that are the
source of computational intractability, structural graph theory) and Algorithms (exact resolution, approximation with performance guarantee, and heuristics).

Members

Projects 

The Optimization, Structure & Algorithms group’s three main scientific projects deal with the multifaceted field of optimization from different and complementary perspectives: graphs (for modeling and exploiting underlying structures), parameterized complexity (for understanding which intrinsic dimension of a problem makes it computationally hard), approximation (for balancing worst-case quality of a solution and running time), mathematical programming (for exploiting the geometrical properties of combinatorial problems), robustness (for facing uncertainty on the input data), heuristics (for quickly providing operational solutions to hard real-life problems). The Optimization, Structure & Algorithms group members also significantly participates in other scientific projects of LAMSADE such as MOCO, Social Choice and Game Theory, and MILES.

 

Seminars

 

AGaPe and Mathis are the main scientific projects of the pole, they have in common to study the relaxations of NP-hard problems. The relaxation relates to the structure of the instances under consideration (Mathis / AGaPe), the set of feasible solutions (Mathis), the optimality of the solution provided (AGaPe / Mathis), and the time it takes to obtain it (AGaPe). The projects also study the generalizations of polynomial problems. The generalization relates to optimality criteria (Multicriteria), the optimization of competing criteria (Games), data dynamics (Services), and data reliability (Mathis).

Links :

Production systems, telecommunications, simulation of dynamic movements, Web Services, multimedia data processing, management of digital music libraries, etc.

Mathematical programming (linear and integer programming, polyhedral approaches in combinatorial optimization), polynomial and weakly exponential approximation (parameterized complexity, FPT algorithms), robustness (stochastic optimization, evolutionary instances, on-line algorithmic, reoptimization ), Optimization for big data, metaheuristics, simulation, logistics chains, optimization of resources and production of services.