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

$\mathrm{\forall }(u,v)\in E:\sum _{i=1}^k{f}_i(u,v)\cdot d_i\le 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.

$\mathrm{\forall }i\in [[1,k]],\mathrm{\forall }u\in V\setminus \{s_i,t_i\}:\sum _{w\in V}{f}_i(u,w)-\sum _{w\in V}{f}_i(w,u)=0$

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

$\mathrm{\forall }i\in [[1,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.

$\mathrm{\forall }i\in [[1,k]]:\sum _{w\in V}{f}_i(w,t_i)-\sum _{w\in V}{f}_i(t_i,w)=1$

Problèmes d'optimisation

Plusieurs problèmes d'optimisation correspondent ont été proposésModèle:Référence 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)=\frac{\sum _{i=1}^k{f}_i(u,v)d_i}{c(u,v)}$.

Le problème peut être résolu en minimisant $\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

$\mathrm{\forall }(u,v)\in E:U_{max}\ge 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 $\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 $\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/

Modèle:Portail