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[réf. nécessaire].

  • 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