Optimisation bi-niveau et ordonnancement

L'optimisation bi-niveau est un sujet de recherche actuellement en plein développement et les problèmes qui se posent sont extrêmement compliqués à résoudre. Cette famille de problèmes peut s'énoncer très simplement : soient deux agents, le leader et le follower. Tous les deux ont à prendre des décisions pour résoudre le problème d'optimisation. Le leader, qui prend en premier ses décisions, a son propre objectif à satisfaire. Puis, tenant compte des décisions prises, le follower doit ensuite prendre ses décisions pour satisfaire son propre objectif. On suppose que ces deux ensembles de décisions sont disjoints. Par exemple, en ordonnancement, le leader peut décider des travaux à ordonnancer parmi un ensemble de départ, et le follower peut décider de la façon de les ordonnancer. 

Très peu de résultats sont connus en ordonnancement et les problèmes qui se posent sont très difficiles à résoudre d'un point de vue exact. Dans ce séminaire, nous verrons quelques cadres pratiques pouvant mettre en jeu des problèmes d'ordonnancement bi-niveau, ainsi que de premiers résultats dans des cas simples. Cela sera aussi l'occasion d'une escapade en théorie de la complexité, où nous verrons que ces problèmes sont potentiellement bien plus difficile que tous les problèmes NP-difficiles.