Program > By author > Salch Alexandre

Le problème que nous étudions a pu être observé dans le cadre de nos travaux sur le rétablissement des opérations aériennes. Il est intéressant de voir un problème industriel pratique dont la modélisation se ramène à un problème de graphe de prime abord très théorique.

Le problème consiste à affecter des dates à des intervalles de temps, décrivant la disponibilité de certaines ressources. Une date ne peut être affectée qu'à un seul intervalle et un intervalle contient au plus une date. L'état initial de notre problème consiste en une affectation partielle des dates aux intervalles. Il reste des dates et des intervalles libres. L'objectif est de trouver une affectation maximisant le nombre de dates affectées. Cependant des contraintes légales viennent se greffer à ce problème : 1) quand une date ou un intervalle est affecté, on peut le réaffecter mais pas le libérer ; 2) on peut échanger au plus k dates en même temps.

Nous modélisons ce problème comme un graphe biparti G=((U,V),E) tel que U représente l'ensemble des dates, V l'ensemble des intervalles, et une arête (u,v) appartient à E si et seulement si la date u est incluse dans l'intervalle v. L'affectation initiale est alors un couplage quelconque. L'objectif est de trouver un couplage de cardinalité maximum, en partant du couplage initial et en appliquant des chemins augmentant dont le nombre d'arêtes est inférieur à k. On appellera un tel couplage un couplage k-maximum.

Nous chercherons à répondre à plusieurs questions ouvertes à notre connaissance concernant ce nouveau problème. Tout d'abord, concernant la complexité du problème, en considérant un couplage k-maximum, nous perdons le certificat d'optimalité du couplage maximum (l'absence de chaîne augmentante). Puis nous essaierons de caractériser les instances pratiques de ce problème et de donner un algorithme de résolution pour k égal 2 ou 3.