Theme Combinatorial optimization


This theme involves modelling and research into efficient algorithms for various optimisation problems arising from operations research and applied mathematics. The application context is very broad, ranging from continuous to discrete, from deterministic to stochastic, from graphs to algorithmic complexity.
 The nature of the optimisation problems studied is :

    Combinatorial: finding the smallest or largest element from a finite set of elements. Variables take integer values.

    Continuous: find the smallest or largest point in a non-countable infinite set. Variables can take real values.

Combinatorial optimisation problems are studied using several approaches depending on their difficulty and structure:

  • Polyhedral approaches: the aim is to reduce the problem to the solution of a linear programme. This task is impossible when the problem in question is NP-complete, but the determination of a relaxed linear program is easy and generally offers very useful bounds for starting the solution using branch-and-bound-and-cut algorithms. These are the best-performing exact algorithms for solving difficult combinatorial optimisation problems. This approach is also used to describe instances where an NP-complete problem becomes polynomial. This is achieved by completely describing the polytope associated with the problem by a linear program with constraints that are easy to separate (we can introduce the constraints needed for optimisation in polynomial time despite their exponential number in most cases).
  • Approximation algorithms: this involves developing polynomial algorithms in which the value of the solution found is analytically comparable to the value of the optimal solution. The measure taken is the worst-case approximation ratio between the value found and the value of the optimum. Average approximation ratio measures are also considered where this can be defined.
  • Game algorithms: This involves combining mathematics, economics and computer science to manage situations where individual interests conflict with the common welfare. The application of algorithms is recent: the aim is to find the right strategies to ensure stability in exchanges between individuals and in the sharing of common resources. Game algorithms emphasise the complexity of calculating these equilibria and rely on performance-guaranteed bounds and approximations to respond to models whose exact solutions are unrealistic or unknown.
  • Stochastic and robust optimisation: In many applications, the data is not known exactly. The associated uncertainty is often represented by several scenarios. These different scenarios are usually modelled by adding new variables and constraints.

The problems studied come from a variety of fields: transport networks, telecommunication networks, electricity networks, bioinformatics, sensor networks, infrastructure localisation, nuclear and automotive.

Last publications

Fatiha Bendali, Jean Mailfert, Eloise Mole Kamga, Alain Quilliot, Hélène Toussaint - Sept. 5, 2023
Models, Algorithms and Approximation Results for a Bi-Level Synchronized Knapsack Problem
Cybernetics and Systems

Thi Quynh Trang Vo, Mourad Baiou, Viet Hung Nguyen, Paul Weng - June 4, 2023
Improving Subtour Elimination Constraint Generation in Branch-and-Cut Algorithms for the TSP with Machine Learning
17th learning and intelligent optimization conference

Thi Quynh Trang VO, Mourad Baiou, Viet Hung Nguyen - May 22, 2023
A Branch-and-Cut algorithm for the Balanced Traveling Salesman Problem

Minh Hieu Nguyen, Mourad Baiou, Viet Hung Nguyen - March 2, 2023
Determining the generalized Nash Fairness solution set for Bi-Objective Discrete Optimization

Aurélien Mombelli, Alain Quilliot, Mourad Baiou - Feb. 21, 2023
A Comparison of Several Speed Computation Methods for the Safe Shortest Path Problem

Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret Wagler - Feb. 9, 2023
On Three Domination-Based Identification Problems in Block Graphs
9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023)

Mourad Baïou, Francisco Barahona - Feb. 1, 2023
On some algorithmic aspects of hypergraphic matroids
Discrete Mathematics

Sylvie Alayrangues, Olivier Baudon, Sylvain Beauvoir, Emmanuel Beffara, Sébastien Daniel, Christophe Declercq, Anne Héam, Philippe Marquet, Jean-Christophe Masseron, Antoine Meyer, Malika More, Florence Nény, Cécile Prouteau, Sylviane Schwer, Jean-Marc Vincent, Emmanuel Volte, Aslı Grimaud - Jan. 31, 2023
Une analyse des exercices d'algorithmique et de programmation des DNB

Christian Laforest, Timothée Martinod - Jan. 1, 2023
Introduction to Routing Problems with Mandatory Transitions

José-L. Figueroa, Alain Quilliot, Hélène Toussaint, Annegret Wagler - Jan. 1, 2023
Optimal Paths with Impact on a Constraint System: An Application to the 1-Request Insertion for the Pickup and Delivery Problem with Transfers
SN Computer Science

All publications are here