Thème Optimisation Combinatoire

Présentation

Ce thème concerne la modélisation et la recherche d’algorithmes efficaces pour différents problèmes d’optimisation issus de la recherche opérationnelle et des mathématiques appliquées. Le contexte applicatif est très large, allant du continu au discret, du déterministe au stochastique, des graphes aux modèles variationnels.
La nature des problèmes d’optimisation étudiés est :

  • Combinatoire : trouver le plus petit ou le plus grand élément parmi un ensemble fini d’éléments. Les variables prennent alors des valeurs entières.
  • Continue : trouver le plus petit ou plus grand point d’un ensemble infini non-dénombrable. Les variables peuvent prendre des valeurs réelles.

Les problèmes d’optimisation sont étudiés à travers plusieurs approches selon leurs difficultés et leurs structures :

  • Approches polyédrales : il s’agit de ramener le problème à la résolution d’un programme linéaire. Cette tâche est impossible quand le problème en question est NP-complet, mais la détermination d’un programme linéaire relaxé est facile et offre en général des bornes très utiles pour entamer la résolution par des algorithmes de branch-and-bound-and-cut. Ce sont les algorithmes exactes les plus performants pour résoudre les problèmes d’optimisation combinatoire difficiles. Cette approche est aussi utilisée pour décrire des instances où un problème NP-complet devient polynomial. Ceci est réalisé en décrivant complètement le polytope associé au problème par un programme linéaire avec des contraintes faciles à séparer (nous pouvons introduire en un temps polynomial les contraintes nécessaires à l’optimisation malgré leur nombre exponentiel dans la plupart des cas).
  • Algorithmes d'approximation : il s'agit ici de proposer, pour des problèmes difficiles, des algorithmes produisant en temps polynomial des solutions dont on peut analytiquement garantir la qualité (sa taille, son poids, etc.) par rapport à la solution optimale.   
  • Les extensions de la notion de convexité, la relation entre optimalité globale et optimalité locale. On s’attache ici à rapprocher les modèles non convexes des modèles combinatoires par différentes reformulations.
  • Les schémas de décomposition primale et duale des systèmes complexes. 

Les problèmes étudiés sont issus de divers domaines : réseaux de transport, réseaux de télécommunication, réseaux électriques, bio-informatique, réseaux de capteurs, localisation des infrastructures, nucléaire, automobile.

Dernières Publications

Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub - 15 juillet 2021
Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem


Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub - 15 juillet 2021
On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part I


Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub - 15 juillet 2021
Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem


Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub - 15 juillet 2021
On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II


Fatiha Bendali, Eloise Mole Kamga, Jean Mailfert, Alain Quilliot, Hélène Toussaint - 1 juillet 2021
Pipe-lining dynamic programming processes to synchronize both the production and the consumption of energy
RAIRO - Operations Research

Fatiha Bendali, Eloise Mole Kamga, Jean Mailfert, Alain Quilliot, Hélène Toussaint - 1 juillet 2021
Synchronizing energy production and vehicle routing
RAIRO - Operations Research

Rafael Colares, Hervé Kerivin, Annegret Wagler - 2 mars 2021
An extended formulation for the Constraint Routing and Spectrum Assignment Problem in Elastic Optical Networks *


Hussein Chouman, Annie Gravey, Philippe Gravey, Youssouf Hadhbi, Hervé Kerivin, Michel Morvan, Annegret Wagler - 2 mars 2021
Impact of RSA Optimization Objectives on Optical Network State


Rafael Colares, Mourad Baïou, Hervé Kerivin - 25 janvier 2021
The complexity of the Unit Stop Number Problem and its implications to other related problems


Rui Sá Shibasaki, Mourad Baïou, Francisco Barahona, Philippe Mahey, Mauricio Souza - 1 janvier 2021
Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods
International Transactions in Operational Research

Toutes les publis se trouvent ici

Projets