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 à la complexité algorithmique.
 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 combinatoire 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 exacts 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 de développer des algorithmes polynomiaux dont la valeur de la solution trouvée est comparable analytiquement à la valeur de la solution optimale. La mesure prise est le rapport d’approximation en pire cas, entre la valeur trouvée et la valeur de l’optimal. Des mesures de rapports d’approximation en moyenne sont aussi considérées lorsque cela peut être défini.

  • Algorithmique des jeux : Il s’agit d’allier les mathématiques, l’économie et l’informatique pour gérer des situations de conflits d’intérêt individuel avec l’intérêt commun. L’application des algorithmes est récente : il s’agit de trouver les bonnes stratégies qui assurent une stabilité lors des échanges entre individus et des partages de ressources communes entre eux. L’algorithmique des jeux met l’accent sur la complexité du calcul de ces équilibres et s’appuie sur des bornes et approximations à performance garantie pour répondre à des modèles dont les solutions exactes sont irréalistes ou inconnues.

  • Optimisation stochastique et robuste : Dans de nombreuses applications les données ne sont pas connues avec exactitude. L’incertitude associée est souvent représentée par plusieurs scénarios. Ces différents scénarios sont en général modélisés par l’ajout de nouvelles variables et contraintes.

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

Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael Henning, Annegret Wagler - 1 décembre 2024
Progress towards the two-thirds conjecture on locating-total dominating sets
Discrete Mathematics

Victoria Kaial, Hervé Kerivin, Annegret K Wagler - 1 novembre 2024
On non-superperfection of edge intersection graphs of paths
Discrete Optimization

Duy Dao Do, Hervé Kerivin, Philippe Lacomme, Bogdan Vulpescu - 31 octobre 2024
Comparative study of quantum methods in the resolution of track findings instances


José Luis Figueroa González, Mourad Baiou, Alain Quilliot, Hélène Toussaint, Annegret Wagler - 1 octobre 2024
A project and lift approach for a 2-commodity flow relocation model in a time expanded network
Discrete Applied Mathematics

Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret K Wagler - 22 juillet 2024
On three domination-based identification problems in block graphs
Fundamenta Informaticae

Thanh Loan Nguyen, Viet Hung Nguyen, Minh Hieu Nguyen, Thi Viet Thanh Vu - 7 juillet 2024
On the Kalai-Smorodinsky solutions for Bi-objective Spanning Tree Problem


Huy Phuc Nguyen Ha, Viet Hung Nguyen, Anh Son Ta - 4 juin 2024
Solving Edge-Weighted Maximum Clique Problem with DCA Warm-Start Quantum Approximate Optimization Algorithm
Metaheuristics International Conference (MIC 2024)

Huy Phuc Nguyen Ha, Viet Hung Nguyen, Anh Son Ta - 4 juin 2024
Solving Quadratic Knapsack Problem with Biased Quantum State Optimization Algorithm
Metaheuristics International Conference (MIC 2024)

Dipayan Chakraborty, Annegret Wagler - 22 mai 2024
Open-Separating Dominating Codes in Graphs
International Symposium on Combinatorial Optimization

Fatiha Bendali, Alejandro Olivas Gonzales, Alain Quilliot, Hélène Toussaint - 22 mai 2024
Surrogate Constraints for Synchronized Energy Production/Consumption


Toutes les publis se trouvent ici