Yerim Chung (Paris 1)

Travail réalisé en collaboration avec Marc Demange.

Les problèmes combinatoires inverses constituent une classe particulière de problèmes d’optimisation combinatoire apparaissant dans de nombreux domaines, de la physique aux sciences de gestion. Au lieu de suivre une problématique classique visant à déterminer une/les solutions optimale(s) d’un problème donné, l’objectif d’un problème inverse est, connaissant une solution réalisable particulière d’un problème paramétré fixé, de modifier le moins possible au sens d’une norme donnée, les paramètres du modèle pour rendre cette solution optimale. Plusieurs problèmes combinatoires ont été étudiés sous cet angle, notamment des problème formulés par la programmation linéaire dont la version inverse peut être résolue par dualité. C’est ainsi que les problèmes de cheminement inverses, de flots ou encore d’arbre couvrant ont été largement étudiés depuis 20 ans.

Nous proposons trois variantes de tels problèmes. Dans un premier temps, en offrant la possibilité de contraindre les systèmes de paramètres, en particulier par des contraintes discrètes (contrainte d’intégrité, booléenne, …), le problème inverse devient lui-même un problème combinatoire. Ce cadre offre notamment la possibilité de formuler des problèmes dont l’objectif est de modifier la structure de l’instance pour rendre une solution fixée optimale. La seconde variante consiste à modifier l’instance, non pas pour rendre la solution fixée optimale, mais pour forcer un algorithme fixé, optimal ou pas, à la choisir. Enfin, l’objectif de la troisième problématique est, étant donné une valeur (et non une solution réalisable), de forcer cette valeur optimale de l’instance transformée.

Nous étudions ces problématiques pour les problèmes de stable maximum, de voyageur de commerce minimum et de coloration minimum de graphes. Nous motivons ces problèmes par plusieurs modèles et étudions la complexité et les possibilités de résolution efficace des problèmes correspondants.