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

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

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

${\displaystyle \forall i\in [\![1,k]\!],\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.

${\displaystyle \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.

${\displaystyle \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és^{[réf. nécessaire]}.

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

${\displaystyle 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 \displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$. Une linéarisation fréquente de ce problème consiste à minimiser l'utilisation maximale ${\displaystyle U_{max}}$, avec

${\displaystyle \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 ${\displaystyle a(u,v)f(u,v)}$ à tout envoi de flots sur ${\displaystyle (u,v)\in E}$.

Ensuite, il faut minimiser ${\displaystyle \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 \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/

• Portail des mathématiques
• Portail de l'informatique théorique