Flots de coût minimum.

De nombreux problèmes (provenant parfois d'autres domaines que les graphes) peuvent se ramener à des problèmes de flots maximum dans les graphes (max flow) pour lesquels il existe des algorithmes polynomiaux très performants. Il existe une généralisation très intéressante des problèmes de flots maximum, qui couvre encore plus d'applications : les problèmes de flot de coût minimum (min-cost flow). Les contraintes sont proches de celles des max flows, mais avec quelques différences (comme les coûts sur les arcs).

L'objectif ici est de présenter la problématique des flots de coût minimum, en particulier l'aspect algorithmique, et de faire le lien avec des problèmes connus. Les questions qui suivent peuvent servir de guide :

• Présenter les problèmes de flot de coût minimum.
• Y a-t-il un lien avec la programmation linéaire ?
• Quelles sont les différences avec les contraintes des problèmes de flot maximum ?
• Montrer que les problèmes de flot maximum ou ceux de plus courts chemins, peuvent se ramener à des problèmes de flots de coût minimum.
• Donner au moins un autre exemple d'application, par exemple le problème de transport maritime (ship loading problem).
• Donner au moins un algorithme (pseudo-polynomial suffit, càd. on peut avoir des valeurs des contraintes en complexité et non pas leur logarithme).
  

Remarque: il existe des algorithmes (fortement) polynomiaux, par exemple un algorithme de Tardos, pour résoudre les problèmes de flots de coût minimum, mais c'est plus difficile.

Une référence (pas exhaustif).

• Digraphs: theory, algorithms and applications, livre de J. Bang-Jensen et G. Gutin, Springer (2002). Voir la section 3.10.

Retour à la page des sujets.