Problème de flot multi-commodités
Le problème de flot multi-commodités est un problème de réseau de flot avec plusieurs commodités sur le même graphe, c'est-à-dire qu'il y a plusieurs demandes de flot entre des paires de nœuds source et puits. Ce problème généralise le cadre du problème du flot maximum.
Définition
Soit un réseau de flot , où chaque arête a une capacité. Soit le nombre de commodités sur le réseau, on définit ces commodités , tel que , avec et qui sont respectivement la source et le puits de la commodité , enfin est la demande de cette commodité. On note la proportion du flot passant par l'arête. On a si le flot est séparé en plusieurs chemins, sinon. Le problème de flot multi-commodités consiste à trouver les variables de flot qui satisfont les contraintes suivantes :
(1) Capacité des arêtes : Le flot total sur une arête ne doit pas excéder la capacité de cette arête
(2) Conservation du flot dans les nœuds intermédiaire : Pour chaque nœud intermédiaire , le flot total entrant est égal au flot total sortant.
- où K = [1..k]
(3) Conservation du flot des sources : Chaque source doit émettre tout son flot.
(4) Conservation du flux des puits : Chaque puits doit recevoir tout son flot.
Problèmes d'optimisations
Plusieurs problèmes d'correspondent ont été proposés.
- Dans le problème d'équilibrage des charges, le but est d'acheminer les flux tels que l'utilisation de tous les liens soit la même. On définit :
.
Le problème peut être résolu en minimisant . Une linéarisation fréquente de ce problème consiste à minimiser l'utilisation maximale , avec
.
- Dans le problème de flot multi-commodités minimum, il y a un coût à tout envoi de flots sur .
Ensuite, il faut minimiser .
- Dans le problème de flot multi-commodités maximal, la demande de chaque commodité n'est pas fixé, le flot traversant le graphe doit être maximisé en maximisant la somme des demandes .
Classe de complexité
Le problème qui consiste à décider si un réseau de flot peut satisfaire toutes les demandes des commodités est NP-complet pour des flots à valeur entière et est dans P pour des flots à valeur fractionnaire.
Application
Le problème de flot multi-commodités permet de modéliser de nombreux problèmes de la vie courante. Il peut par exemple modéliser un réseau ferroviaire où chaque axe a une capacité et plusieurs couples de gares doivent s'échanger de la marchandise. Un autre exemple est la modélisation de réseaux téléphoniques, où chaque liaison a une bande passante maximum et des couples de nœuds veulent s'envoyer une certaine quantité de données.
Ressources externes
- Article de Clifford Stein sur ce problème : http://www.columbia.edu/~cs2035/papers/#mcf
- Logiciel résolvant ce problème : https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/