Problème de flux de réseau

En optimisation combinatoire , les problèmes de flux de réseau sont une classe de problèmes de calcul dans lesquels l'entrée est un réseau de flux (un graphe avec des capacités numériques sur ses arêtes), et le but est de construire un flux , des valeurs numériques sur chaque arête qui respectent les contraintes de capacité et qui ont un flux entrant égal au flux sortant à tous les sommets, sauf pour certains terminaux désignés.

Les problèmes de flux de réseau comprennent notamment les types suivants :

• Le problème du débit maximal , dont l'objectif est de maximiser la quantité totale de débit sortant des terminaux sources et entrant dans les terminaux puits
• Le problème de flux à coût minimal , dans lequel les arêtes ont des coûts ainsi que des capacités et l'objectif est d'atteindre une quantité de flux donnée (ou un flux maximal) qui a le coût minimal possible
• Le problème des flux multi-produits , dans lequel il faut construire plusieurs flux pour différents produits dont les quantités totales de flux respectent les capacités
• Le flux nulle part nul est un type de flux étudié en combinatoire, dans lequel les quantités de flux sont restreintes à un ensemble fini de valeurs non nulles.

Le théorème du flot maximal et de la coupe minimale établit l'égalité entre la valeur d'un flot maximal et celle d'une coupe minimale , c'est-à-dire une partition des sommets du réseau de flot qui minimise la capacité totale des arêtes traversant la partition. Des théorèmes approchés du flot maximal et de la coupe minimale étendent ce résultat aux problèmes de flot multi-produits. L' arbre de Gomory-Hu d'un réseau de flot non orienté offre une représentation concise de toutes les coupes minimales entre différentes paires de sommets terminaux.

Les algorithmes de construction de flux comprennent

• L'algorithme de Dinic , un algorithme fortement polynomial pour le flot maximal
• L' algorithme d'Edmonds-Karp , un algorithme fortement polynomial plus rapide pour le flux maximal
• L' algorithme de Ford-Fulkerson , un algorithme glouton pour le flot maximal qui n'est généralement pas fortement polynomial.
• L' algorithme du simplexe de réseau , une méthode basée sur la programmation linéaire mais spécialisée pour le flux de réseau
• L' algorithme décalé pour le flux à coût minimal
• L' algorithme de flux maximal push-relabel , l'une des techniques connues les plus efficaces pour le flux maximal

Sinon, le problème peut être formulé comme un programme linéaire plus classique ou similaire et résolu à l'aide d'un solveur d'optimisation à usage général.