La mise en forme de cet article est à améliorer (avril 2021).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Cet article a besoin d’être illustré (mai 2021).

Pour améliorer cet article, des médias (images, animations, vidéos, sons) sous licence libre ou du domaine public sont les bienvenus.
Si vous êtes l’auteur d’un média que vous souhaitez partager, importez-le. Si vous n’êtes pas l’auteur, vous pouvez néanmoins faire une demande de libération d’image à son auteur.

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.

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){\dot {d}}_{i}\leq c(u,v)}$

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

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

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

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

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

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.

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.

• 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