Problème de débit maximum - Maximum flow problem

Réseau de flux pour le problème : Chaque humain (ri) est prêt à adopter un chat (wi1) et/ou un chien (wi2).  Cependant, chaque animal de compagnie (pi) a une préférence pour seulement un sous-ensemble des humains.  Trouvez une correspondance entre les animaux de compagnie et les humains de telle sorte que le nombre maximum d'animaux de compagnie soit adopté par l'un de ses humains préférés.
Réseau de flux pour le problème : Chaque humain (r i ) est prêt à adopter un chat (w i 1) et/ou un chien (w i 2). Cependant, chaque animal de compagnie (p i ) n'a une préférence que pour un sous-ensemble d'humains. Trouvez une correspondance entre les animaux de compagnie et les humains de telle sorte que le nombre maximum d'animaux de compagnie soit adopté par l'un de ses humains préférés.

Dans la théorie de l'optimisation , les problèmes de débit maximal impliquent de trouver un débit réalisable à travers un réseau de débit qui obtient le débit maximal possible.

Le problème de débit maximal peut être considéré comme un cas particulier de problèmes de débit de réseau plus complexes, tels que le problème de circulation . La valeur maximale d'un st flux (c'est-à-dire le flux de la source s au puits t) est égale à la capacité minimale d'une st coupe (c'est-à-dire la coupe séparant s de t) dans le réseau, comme indiqué dans le flux max-min- théorème de coupe .

Histoire

Le problème du débit maximal a été formulé pour la première fois en 1954 par TE Harris et FS Ross comme un modèle simplifié du débit du trafic ferroviaire soviétique.

En 1955, Lester R. Ford, Jr. et Delbert R. Fulkerson ont créé le premier algorithme connu, l'algorithme Ford-Fulkerson . Dans leur article de 1955, Ford et Fulkerson ont écrit que le problème de Harris et Ross est formulé comme suit (voir p. 5) :

Considérons un réseau ferroviaire reliant deux villes par l'intermédiaire d'un certain nombre de villes intermédiaires, où chaque maillon du réseau se voit attribuer un numéro représentant sa capacité. En supposant un état stationnaire, trouvez un débit maximal d'une ville donnée à l'autre.

Dans leur livre Flows in Network , en 1962, Ford et Fulkerson ont écrit :

Elle a été posée aux auteurs au printemps 1955 par TE Harris, qui, en collaboration avec le général FS Ross (à la retraite), avait formulé un modèle simplifié de circulation ferroviaire et identifié ce problème particulier comme le problème central suggéré par le modèle [11].

où [11] fait référence au rapport secret de 1955 Fundamentals of a Method for Evaluating Rail net Capacities de Harris et Ross (voir p. 5).

Au fil des ans, diverses solutions améliorées au problème de débit maximal ont été découvertes, notamment l'algorithme de chemin d'augmentation le plus court d'Edmonds et Karp et indépendamment de Dinitz ; l'algorithme de blocage de flux de Dinitz ; l' algorithme push-relabel de Goldberg et Tarjan ; et l'algorithme de flux de blocage binaire de Goldberg et Rao. Les algorithmes de Sherman et Kelner, Lee, Orecchia et Sidford, respectivement, trouvent un flux maximum approximativement optimal mais ne fonctionnent que dans les graphes non orientés.

En 2013, James B. Orlin a publié un article décrivant un algorithme.

Définition

Un réseau de flux, avec source s et puits t . Les chiffres à côté du bord sont les capacités.

On établit d'abord quelques notations :

  • Soit un réseau avec respectivement la source et le puits .
  • Si est une fonction sur les arêtes de alors sa valeur sur est notée ou

Définition. La capacité d'une arête est la quantité maximale de flux qui peut passer à travers une arête. Formellement c'est une carte

Définition. Un flux est une carte qui satisfait les éléments suivants :

  • Contrainte de capacité . Le débit d'une arête ne peut pas dépasser sa capacité, c'est-à-dire : pour tout
  • Conservation des flux. La somme des flux entrant dans un nœud doit être égale à la somme des flux sortant de ce nœud, à l'exception de la source et du puits. Ou:

Remarque . Les flux sont antisymétriques : pour tous

Définition. La valeur du débit est la quantité de débit passant de la source au puits. Formellement pour un flux, il est donné par :

Définition. Le problème du débit maximal est d'acheminer le plus de débit possible de la source au puits, c'est-à-dire de trouver le débit de valeur maximale.

Notez que plusieurs flux maximum peuvent exister, et si des valeurs arbitraires réelles (ou même rationnelles arbitraires) de flux sont autorisées (au lieu de simplement des entiers), il y a soit exactement un flux maximum, soit une infinité, puisqu'il existe une infinité de combinaisons linéaires de les débits maximaux de base. En d'autres termes, si nous envoyons des unités de flux sur le bord dans un flux maximum et des unités de flux dans un autre flux maximum, alors pour chacun, nous pouvons envoyer des unités et acheminer le flux sur les bords restants en conséquence, pour obtenir un autre flux maximum. Si les valeurs de flux peuvent être des nombres réels ou rationnels, alors il existe une infinité de telles valeurs pour chaque paire .

Algorithmes

Le tableau suivant répertorie les algorithmes permettant de résoudre le problème de débit maximal.

Méthode Complexité La description
Programmation linéaire Contraintes imposées par la définition d'un flux légal . Voir le programme linéaire ici.
Algorithme de Ford-Fulkerson Tant qu'il y a un chemin ouvert à travers le graphe résiduel, envoyer le minimum des capacités résiduelles sur le chemin.

L'algorithme n'est assuré de se terminer que si tous les poids sont rationnels , auquel cas la quantité ajoutée au flux à chaque étape est au moins le plus grand diviseur commun des poids. Sinon, il est possible que l'algorithme ne converge pas vers la valeur maximale. Cependant, si l'algorithme se termine, il est garanti de trouver la valeur maximale.

Algorithme d'Edmonds-Karp Une spécialisation de Ford-Fulkerson, trouvant des chemins d'augmentation avec la recherche en largeur d'abord .
Algorithme de Dinic Dans chaque phase, les algorithmes construisent un graphe en couches avec une recherche en largeur d'abord sur le graphe résiduel . Le débit maximal dans un graphique en couches peut être calculé dans le temps et le nombre maximal de phases est . Dans les réseaux à capacités unitaires, l'algorithme de Dinic se termine dans le temps.
Algorithme MKM (Malhotra, Kumar, Maheshwari) Une modification de l'algorithme de Dinic avec une approche différente pour construire des flux bloquants. Reportez-vous au papier d'origine .
Algorithme de Dinic avec arbres dynamiques La structure de données d' arbres dynamiques accélère le calcul du débit maximal dans le graphique en couches à .
Algorithme général push–relabel L'algorithme push relabel maintient un préflux, c'est-à-dire une fonction de flux avec possibilité d'excès dans les sommets. L'algorithme s'exécute tant qu'il y a un sommet avec un excès positif, c'est-à-dire un sommet actif dans le graphe. L'opération de poussée augmente le flux sur une arête résiduelle, et une fonction de hauteur sur les sommets contrôle à travers laquelle les arêtes résiduelles peuvent être poussées. La fonction de hauteur est modifiée par l'opération de réétiquetage. Les définitions appropriées de ces opérations garantissent que la fonction de flux résultante est un flux maximum.
Algorithme push–relabel avec règle de sélection de sommet FIFO Variante de l'algorithme push-relabel qui sélectionne toujours le sommet le plus récemment actif et effectue des opérations de push tant que l'excès est positif et qu'il existe des arêtes résiduelles admissibles à partir de ce sommet.
Algorithme push–relabel avec règle de sélection de sommet de distance maximale Variante d'algorithme push-relabel qui sélectionne toujours le sommet le plus éloigné de ou (c'est-à-dire le sommet d'étiquette le plus élevé) mais procède autrement comme l'algorithme FIFO.
Algorithme push-relabel avec arbres dynamiques L'algorithme construit des arbres de taille limitée sur le graphe résiduel en ce qui concerne la fonction de hauteur. Ces arbres fournissent des opérations de poussée à plusieurs niveaux, c'est-à-dire une poussée le long d'un chemin de saturation entier au lieu d'un seul bord.
Algorithme de KRT (King, Rao, Tarjan)
Algorithme de flux de blocage binaire La valeur U correspond à la capacité maximale du réseau.
Algorithme de James B Orlin + KRT (King, Rao, Tarjan) Algorithme de Orlin de résoud max flux en temps pour tout KRT résout en pour .
Algorithme de Kathuria-Liu-Sidford Méthodes de points intérieurs et renforcement des bords à l'aide de flux -norm. S'appuie sur l'algorithme antérieur de Madry, qui a atteint le runtime .
Algorithme BLNPSSSW / BLLSSSW

Méthodes des points intérieurs et maintien dynamique des flux électriques avec décompositions d'expanseurs.
Algorithme de Gao-Liu-Peng L'algorithme de Gao, Liu et Peng s'articule autour du maintien dynamique des flux électriques croissants au cœur de l'algorithme basé sur la méthode des points intérieurs de [Mądry JACM '16]. Cela implique de concevoir des structures de données qui, dans des paramètres limités, renvoient des bords avec une grande énergie électrique dans un graphique soumis à des mises à jour de résistance.

Pour des algorithmes supplémentaires, voir Goldberg & Tarjan (1988) .

Théorème d'écoulement intégral

Le théorème du flux intégral dit que

Si chaque bord dans un réseau de flux a une capacité intégrale, alors il existe un flux maximal intégral.

L'affirmation n'est pas seulement que la valeur du flux est un entier, qui découle directement du théorème max-flow min-cut , mais que le flux sur chaque arête est intégral. Ceci est crucial pour de nombreuses applications combinatoires (voir ci-dessous), où le flux à travers une arête peut coder si l'élément correspondant à cette arête doit être inclus ou non dans l'ensemble recherché.

Application

Problème de débit maximum multi-sources multi-puits

4.1.1. Transformation d'un problème de flux maximum multi-sources multi-puits en un problème de flux maximum à source unique et puits unique

Étant donné un réseau avec un ensemble de sources et un ensemble de puits au lieu d'une seule source et d'un puits, nous devons trouver le débit maximal à travers . Nous pouvons transformer le problème multi-source multi-puits en un problème de flux maximal en ajoutant une source consolidée se connectant à chaque sommet en et un puits consolidé connecté par chaque sommet en (également connu sous le nom de supersource et supersink ) avec une capacité infinie sur chaque bord ( Voir la figure 4.1.1.).

Correspondance bipartite de cardinalité maximale

4.3.1. Transformation d'un problème d'appariement bipartite maximal en un problème de flux maximal

Étant donné un graphe bipartite , nous devons trouver une correspondance de cardinalité maximale dans , c'est-à-dire une correspondance qui contient le plus grand nombre possible d'arêtes. Ce problème peut être transformé en un problème de flux maximum en construisant un réseau , où

  1. contient les arêtes dirigées de à .
  2. pour chacun et pour chacun .
  3. pour chacun (Voir Fig. 4.3.1).

Ensuite, la valeur du flux maximal dans est égale à la taille de la correspondance maximale dans , et une correspondance de cardinalité maximale peut être trouvée en prenant les arêtes qui ont un flux dans un flux maximal intégral.

Couverture minimale du chemin dans un graphe acyclique orienté

Étant donné un graphe acyclique orienté , nous devons trouver le nombre minimum de chemins sommets disjoints pour couvrir chaque sommet dans . On peut construire un graphe bipartite à partir de , où

  1. .

Ensuite, il peut être montré qui a une correspondance de taille si et seulement si a une couverture de chemin disjointe par sommets contenant des arêtes et des chemins, où est le nombre de sommets dans . Par conséquent, le problème peut être résolu en trouvant la correspondance de cardinalité maximale à la place.

Intuitivement, si deux sommets correspondent dans , alors l'arête est contenue dans . Il est clair que le nombre d'arêtes dans est . Pour voir que c'est vertex-disjoint, considérez ce qui suit :

  1. Chaque sommet dans peut être non apparié dans , auquel cas il n'y a pas d'arêtes qui partent dans ; ou il peut être adapté , dans ce cas , il y a exactement un bord en laissant dans . Dans les deux cas, pas plus d'une arête ne laisse un sommet dans .
  2. De même pour chaque sommet in – s'il correspond, il y a une seule arête entrante dans in ; sinon n'a pas de fronts entrants dans .

Ainsi, aucun sommet n'a deux arêtes entrantes ou sortantes dans , ce qui signifie que tous les chemins dans sont disjoints par sommet.

Pour montrer que la couverture a la taille , nous commençons avec une couverture vide et la construisons progressivement. Pour ajouter un sommet à la couverture, nous pouvons soit l'ajouter à un chemin existant, soit créer un nouveau chemin de longueur zéro à partir de ce sommet. Le premier cas s'applique à chaque fois qu'un chemin dans la couverture commence à , ou et qu'un chemin se termine à . Ce dernier cas est toujours applicable. Dans le premier cas, le nombre total de bords de la couverture est augmenté de 1 et le nombre de chemins reste le même ; dans ce dernier cas, le nombre de chemins est augmenté et le nombre d'arêtes reste le même. Il est maintenant clair qu'après avoir couvert tous les sommets, la somme du nombre de chemins et d'arêtes dans la couverture est . Par conséquent, si le nombre de bords dans la couverture est , le nombre de chemins est .

Débit maximal avec des capacités de sommet

4.4.1. Transformation d'un problème de flux maximum avec contrainte de capacités de sommet en problème de flux maximum d'origine par division de nœuds

Soit un réseau. Supposons qu'il existe une capacité à chaque nœud en plus de la capacité de bord, c'est-à-dire une application telle que le flux doit satisfaire non seulement la contrainte de capacité et la conservation des flux, mais également la contrainte de capacité du sommet

En d'autres termes, la quantité de flux passant par un sommet ne peut pas dépasser sa capacité. Pour trouver le débit maximal traversant , nous pouvons transformer le problème en problème de débit maximal au sens original en développant . Tout d'abord, chacun est remplacé par et , où est connecté par les arêtes entrant et est connecté aux arêtes sortant de , puis assigne la capacité à l'arête reliant et (voir Fig. 4.4.1). Dans ce réseau étendu, la contrainte de capacité de sommet est supprimée et le problème peut donc être traité comme le problème de débit maximal d'origine.

Nombre maximum de chemins de s à t

Étant donné un graphe orienté et deux sommets et , nous devons trouver le nombre maximum de chemins de à . Ce problème a plusieurs variantes :

1. Les chemins doivent être bord-disjoints. Ce problème peut être transformé en un problème de flux maximal en construisant un réseau à partir de , avec et étant respectivement la source et le puits de , et en attribuant à chaque bord une capacité de . Dans ce réseau, le débit maximum est ssi il y a des chemins à bords disjoints.

2. Les chemins doivent être indépendants, c'est-à-dire vertex-disjoints (sauf pour et ). Nous pouvons construire un réseau à partir de capacités de sommet, où les capacités de tous les sommets et de toutes les arêtes sont . Alors la valeur du débit maximum est égale au nombre maximum de chemins indépendants de à .

3. En plus du fait que les chemins sont arête-disjoints et/ou sommets disjoints, les chemins ont également une contrainte de longueur : on ne compte que les chemins dont la longueur est exactement , ou au plus . La plupart des variantes de ce problème sont NP-complets, à l'exception des petites valeurs de .

Problème de fermeture

Une fermeture d'un graphe orienté est un ensemble de sommets C , tel qu'aucune arête ne quitte C . Le problème de fermeture est la tâche de trouver la fermeture de poids maximum ou de poids minimum dans un graphe dirigé pondéré par les sommets. Il peut être résolu en temps polynomial en utilisant une réduction au problème de débit maximum.

Applications du monde réel

Élimination du baseball

Construction d'un flux de réseau pour le problème d'élimination du baseball

Dans le problème de l'élimination du baseball , il y a n équipes en compétition dans une ligue. À une étape spécifique de la saison de la ligue, w i est le nombre de victoires et r i est le nombre de matchs restant à jouer pour l'équipe i et r ij est le nombre de matchs restant contre l'équipe j . Une équipe est éliminée si elle n'a aucune chance de terminer la saison en premier. La tâche du problème d'élimination du baseball est de déterminer quelles équipes sont éliminées à chaque moment de la saison. Schwartz a proposé une méthode qui réduit ce problème à un débit de réseau maximal. Dans cette méthode, un réseau est créé pour déterminer si l'équipe k est éliminée.

Soient G = ( V , E ) un réseau avec s , tV étant la source et le puits , respectivement. On ajoute un nœud de jeu ij – qui représente le nombre de jeux entre ces deux équipes. Nous ajoutons également un nœud d'équipe pour chaque équipe et connectons chaque nœud de jeu { i , j } avec i < j à V , et connectons chacun d'eux de s par une arête de capacité r ij - qui représente le nombre de jeux entre ces deux équipes. Nous ajoutons également un nœud d'équipe pour chaque équipe et connectons chaque nœud de jeu { i , j } avec deux nœuds d'équipe i et j pour nous assurer que l'un d'eux gagne. On n'a pas besoin de restreindre la valeur du débit sur ces bords. Enfin, les arêtes sont constituées du nœud d'équipe i au nœud de puits t et la capacité de w k + r kw i est définie pour empêcher l'équipe i de gagner plus que w k + r k . Soit S l'ensemble de toutes les équipes participant à la ligue et soit

.

Dans cette méthode, il est affirmé que l'équipe k n'est pas éliminée si et seulement si une valeur de flux de taille r ( S − { k }) existe dans le réseau G . Dans l'article mentionné, il est prouvé que cette valeur de débit est la valeur de débit maximale de s à t .

Planification des compagnies aériennes

Dans l'industrie du transport aérien, un problème majeur est la planification des équipages de conduite. Le problème d'ordonnancement des compagnies aériennes peut être considéré comme une application du flux de réseau maximal étendu. L'entrée de ce problème est un ensemble de vols F qui contient les informations sur où et quand chaque vol part et arrive. Dans une version de l'ordonnancement des compagnies aériennes, l'objectif est de produire un horaire réalisable avec au plus k équipages.

Afin de résoudre ce problème, on utilise une variante du problème de circulation appelée circulation limitée qui est la généralisation des problèmes de flux de réseau , avec en plus la contrainte d'une borne inférieure sur les flux de bord.

Soient G = ( V , E ) un réseau avec s , tV comme source et les noeuds de puits. Pour la source et la destination de chaque vol i , on ajoute deux nœuds à V , le nœud s i comme source et le nœud d i comme nœud de destination du vol i . On ajoute aussi les arêtes suivantes à E :

  1. Une arête de capacité [0, 1] entre s et chaque s i .
  2. Une arête de capacité [0, 1] entre chaque d i et t .
  3. Un bord ayant une capacité [1, 1] entre chaque paire de s i et D i .
  4. Une arête de capacité [0, 1] entre chaque d i et s j , si la source s j est accessible avec un temps et un coût raisonnables depuis la destination du vol i .
  5. Une arête de capacité [0, ] comprise entre s et t .

Dans la méthode mentionnée, il est affirmé et prouvé que trouver une valeur de flux de k dans G entre s et t est égal à trouver un programme réalisable pour l'ensemble de vols F avec au plus k équipages.

Une autre version de la planification des compagnies aériennes consiste à trouver le minimum d'équipages nécessaires pour effectuer tous les vols. Afin de trouver une réponse à ce problème, un graphe bipartite G' = ( AB , E ) est créé où chaque vol a une copie dans l'ensemble A et l'ensemble B . Si le même plan peut effectuer un vol j après le vol i , iA est reliée à jB . Un appariement dans G' induit un horaire pour F et évidemment l'appariement bipartite maximum dans ce graphe produit un horaire de compagnie avec un nombre minimum d'équipages. Comme il est mentionné dans la partie Application de cet article, la correspondance bipartite à cardinalité maximale est une application du problème de flux maximal.

Problème circulation-demande

Il y a des usines qui produisent des marchandises et des villages où les marchandises doivent être livrées. Ils sont reliés par un réseau de routes, chaque route ayant une capacité c pour le maximum de marchandises pouvant y circuler. Le problème est de trouver s'il existe une circulation qui satisfait la demande. Ce problème peut être transformé en un problème de débit maximum.

  1. Ajouter un nœud source de s et ajouter des bordures de chaque nœud à l'usine f i avec une capacité p ip i est le taux de l' usine de production f i .
  2. Ajoutez un nœud de puits t et ajoutez des tronçons de tous les villages v i à t avec une capacité d id i est le taux de demande du village v i .

Soit G = ( V , E ) ce nouveau réseau. Il existe une circulation qui satisfait la demande si et seulement si :

Valeur de débit maximum ( G ) .

S'il existe une circulation, l'examen de la solution à débit maximal donnerait la réponse quant à la quantité de marchandises à envoyer sur une route particulière pour satisfaire les demandes.

Le problème peut être étendu en ajoutant une borne inférieure sur le flux sur certaines arêtes.


Segmentation des images

Image source de taille 8x8.
Réseau construit à partir du bitmap. La source est à gauche, le puits à droite. Plus un bord est sombre, plus sa capacité est grande. a i est élevé lorsque le pixel est vert, b i lorsque le pixel n'est pas vert. Les pénalités p ij sont toutes égales.

Dans leur livre, Kleinberg et Tardos présentent un algorithme pour segmenter une image. Ils présentent un algorithme pour trouver l'arrière-plan et le premier plan dans une image. Plus précisément, l'algorithme prend en entrée un bitmap modélisé comme suit : a i 0 est la probabilité que le pixel i appartienne au premier plan, b i ≥ 0 la probabilité que le pixel i appartienne à l'arrière-plan, et p ij est le pénalité si deux pixels adjacents i et j sont placés l'un au premier plan et l'autre à l'arrière-plan. Le but est de trouver une partition ( A , B ) de l'ensemble de pixels qui maximise la quantité suivante

,

En effet, pour les pixels en A (considérés comme le premier plan), on gagne a i ; pour tous les pixels de B (considérés comme le fond), on gagne b i . A la frontière, entre deux pixels adjacents i et j , on perd p ij . Cela équivaut à minimiser la quantité

car

Coupe minimale affichée sur le réseau (triangles VS cercles).

Nous construisons maintenant le réseau dont les nœuds sont le pixel, plus une source et un puits, voir la figure à droite. On relie la source au pixel i par une arête de poids a i . Nous connectons le pixel i au puits par une arête de poids b i . Nous connectons le pixel i au pixel j de poids p ij . Maintenant, il reste à calculer une coupure minimale dans ce réseau (ou de manière équivalente un débit maximal). La dernière figure montre une coupe minimale.

Rallonges

1. Dans le problème de flux à coût minimum , chaque arête ( u ,v) a également un coefficient de coût a uv en plus de sa capacité. Si le flux à travers le bord est f uv , alors le coût total est un uv f uv . Il est nécessaire de trouver un flux d'une taille donnée d , au coût le plus faible. Dans la plupart des variantes, les coefficients de coût peuvent être positifs ou négatifs. Il existe différents algorithmes en temps polynomial pour ce problème.

2. Le problème de flux maximum peut être augmenté par des contraintes disjonctives : une contrainte disjonctive négative dit qu'une certaine paire d'arêtes ne peut pas avoir simultanément un flux non nul ; une contrainte disjonctive positive dit que, dans une certaine paire d'arêtes, au moins une doit avoir un flux non nul. Avec des contraintes négatives, le problème devient fortement NP-difficile même pour des réseaux simples. Avec des contraintes positives, le problème est polynomial si les flux fractionnaires sont autorisés, mais peut être fortement NP-difficile lorsque les flux doivent être entiers.


Les références

Lectures complémentaires