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 $G=(V,E)$, où chaque arête $(u,v)\in E$ a une capacité$\,c(u,v)$. Soit$\,k$ le nombre de commodités sur le réseau, on définit ces commodités $K_{1},K_{2},\dots ,K_{k}$, tel que $\,K_{i}=(s_{i},t_{i},d_{i})$, avec $\,s_{i}$ et $\,t_{i}$ qui sont respectivement la source et le puits de la commodité $\,i$, enfin $\,d_{i}$ est la demande de cette commodité. On note$\,f_{i}(u,v)$ la proportion du flot $\,i$ passant par l'arête$\,(u,v)$. On a$\,f_{i}(u,v)\in [0,1]$ si le flot est séparé en plusieurs chemins, $\,f_{i}(u,v)\in \{0,1\}$ 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

$\forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v){\dot {d}}_{i}\leq c(u,v)$

(2) Conservation du flot dans les nœuds intermédiaire : Pour chaque nœud intermédiaire $u$, le flot total entrant est égal au flot total sortant.

$\forall i\in K:\,\sum _{w\in V}f_{i}(u,w)-\sum _{w\in V}f_{i}(w,u)=0\quad \mathrm {quand} \quad u\neq s_{i},t_{i}$où K = [1..k]

(3) Conservation du flot des sources : Chaque source doit émettre tout son flot.

$\forall i\in K:\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1$

(4) Conservation du flux des puits : Chaque puits doit recevoir tout son flot.

$\forall i\in K:\,\sum _{w\in V}f_{i}(w,t_{i})-\sum _{w\in V}f_{i}(t_{i},w)=1$

Problèmes d'optimisations

Plusieurs problèmes d'correspondent ont été proposés^{[réf. nécessaire]}.

• Dans le problème d'équilibrage des charges, le but est d'acheminer les flux tels que l'utilisation $U(u,v)$ de tous les liens $(u,v)\in E$ soit la même. On définit :

$U(u,v)={\dfrac {\sum _{i=1}^{k}f_{i}(u,v)d_{i}}{c(u,v)}}$.

Le problème peut être résolu en minimisant $\displaystyle \sum _{u,v\in V}(U(u,v))^{2}$. Une linéarisation fréquente de ce problème consiste à minimiser l'utilisation maximale $U_{max}$, avec

$\forall (u,v)\in E:U_{max}\geq U(u,v)$.

• Dans le problème de flot multi-commodités minimum, il y a un coût $a(u,v)f(u,v)$ à tout envoi de flots sur $(u,v)\in E$.

Ensuite, il faut minimiser $\displaystyle \sum _{(u,v)\in E}(a(u,v)\sum _{i=1}^{k}f_{i}(u,v))$.

• 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 $\displaystyle \sum _{i=1}^{k}d_{i}$.

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/