Combinatorial Optimization brings together all the theoretical questions originally posed by a certain type of application. The answers are translated into algorithms, the effectiveness of which is measured by experimentation and by the theory of complexity.
Members
The "Optimisation, Structure & Algorithms" pole hosts research around projects :
- AGaPe (Algorithmique à Garanties de Performance)
- Jeux et choix social : aspects axiomatiques et algorithmiques
- Optimisation Combinatoire Multicritère
- Mathis (Programmation Mathématique et Structures Discrètes)
- Multicriteria combinatorial optimization
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.