Min-cost flow.

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 min-cost flow (à traduire ...). 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 min-cost flows, 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 min-cost flow.
• 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 min-cost flow.
• 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 min-cost flow, 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.