MOR - Tema 4

Flujo en redes

Red estándar. Definición

Sea $R_{FS} = (V, A, p)$ red, decimos que es una red estándar si cumple:

• $G = (V, A)$ es un grafo orientado débilmente conexo
• Los pesos $p_{ij}$ para cada arco $(i, j) \in A$ son positivos ($p_{ij} > 0$) y se les denomina capacidad del arco (máxima capacidad del arco)
• Existe un único vértice $F \in V$ tal que $\Gamma^{ - }(F) = \emptyset$ denominado fuente
• Existe un único vértice $S \in V$ tal que $\Gamma^{ + }(S) = \emptyset$ denominado sumidero

Flujo en redes. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, se dice que $f = \{f_{ij}: (i, j ) \in A\}$ colección de reales es un flujo en $R_{FS}$ si cumple:

• Acotación: $0 \leq f_{ij} \leq p_{ij} \quad \forall (i, j) \in A$
• Conservación de flujo: para cada $i \in V$ con $i \neq F, S$:

$$\begin{align*} \displaystyle \sum_{j \in \Gamma^{ + }(i)} f_{ij} - \displaystyle \sum_{k \in \Gamma^{ - }(i)} f_{ki} = 0 \end{align*}$$

Valor del flujo. Definición

Sea $R_{FS} = (V, A, p)$ red estándar y $f = \{f_{ij}: (i, j ) \in A\}$ un flujo en $R_{FS}$, se define el valor del flujo como:

$$\begin{align*} v_f = \displaystyle \sum_{j \in \Gamma^{ + }(F)} f_{Fj} \end{align*}$$

Y en caso de que no haya ambigüedad, es decir, estemos trabajando con una única red y un único flujo, se denota simplemente como $v$.

Existencia de un flujo. Proposición

Sea $R_{FS} = (V, A , p)$ una red estándar, entonces existe al menos un flujo en $R_{FS}$.

Existencia de camino de $F$ a $S$. Proposición

Sea $R_{FS} = (V, A , p)$ una red estándar y $f = \{f_{ij}: (i, j) \in A\}$ un flujo en $R_{FS}$ con valor $v_f > 0$. Entonces, existe al menos un camino elemental de $F$ a $S$ en $R_{FS}$.

Flujo máximo en una red

Conjunto de flujos en una red. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, se define el conjunto de flujos en $R_{FS}$ como:

$$\begin{align*} \mathcal{F} = \{g : g \text{ es un flujo en } R_{FS}\}\\ \end{align*}$$

Flujo máximo en una red. Definición

Sea una red estándar $R_{FS} = (V, A, p)$, la búsqueda del flujo máximo consiste en enviar la cantidad máxima de flujo posible desde la fuente $F$ hasta el sumidero $S$ de forma que se satisfagan las condiciones de acotación y conservación de flujo.

Formalmente, consiste en encontrar un flujo $f* = \{f_{ij}^*: (i, j) \in A\}$ en $R_{FS}$ tal que:

$$\begin{align*} V_{f*} = \max \{v_f: f \in \mathcal{F}\}\\ \end{align*}$$

Cuasicamino. Definición

Sea $R_{FS} = (V, A , P)$ red estándar, un cuasicamino de $i$ a $j$ en $R_{FS}$ es una sucesión alternada de vértices y arcos que forman una cadena elemental en el grafo subyacente de $(V, A)$. Es decir, un cuasicamino $\pi_{ij}$ de $i$ a $j$ es:

$$\begin{align*} \pi_{ij} = i \, e_1 \, i_1 \, e_2 \, i_2 \, \dots i_{k - 1} \, e_k \, i_k \, \dots i_{r - 1} \, e_r \, j\\ \end{align*}$$

Arco positivo y negativo. Definición

Sea $R_{FS} = (V, A , P)$ red estándar, dado un cuasicamino $\pi_{ij}$ de $i$ a $j$ en $R_{FS}$, un arco $e_k$ con $k \neq 1, r$ diremos que es:

• Arco positivo: si está orientado desde $i_{k - 1}$ hacia $i_k$, es decir, $e_k = (i_{k - 1}, i_k) \in A$
• Arco negativo: si está orientado desde $i_k$ hacia $i_{k - 1}$, es decir, $e_k = (i_k, i_{k - 1}) \in A$

Arco saturado. Definición

Sea $R_{FS} = (V, A , P)$ red estándar y $f = \{f_{ij}: (i, j) \in A\}$ un flujo en $R_{FS}$. Un arco $(i, j) \in A$ se dice que está saturado si $f_{ij} = p_{ij}$.

Arco de flujo nulo o libre. Definición

Sea $R_{FS} = (V, A , P)$ red estándar y $f = \{f_{ij}: (i, j) \in A\}$ un flujo en $R_{FS}$. Un arco $(i, j) \in A$ se dice que es de flujo nulo o libre si $f_{ij} = 0$.

Cuasicamino de flujo aumentable. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en $R_{FS}$ y $\pi_{ij} = i \, e_1 \, i_1 \, e_2 \dots i_{k - 1} \, e_k \, i_k \, \dots i_{r - 1} \, e_r \, j$ un cuasicamino de $i$ a $j$ en $R_{FS}$. Decimos que $\pi_{ij}$ es un cuasicamino de flujo aumentable o cuasicamino $f$-aumentable si se cumplen las siguientes condiciones:

$$\begin{align*} \left\{ \begin{array}{ll} f_e < p_e & \forall \text{ arco positivo } e \in \pi_{ij} \, \,(\text{i.e. no está saturado})\\ f_e > 0 & \forall \text{ arco negativo } e \in \pi_{ij} \, \, (\text{i.e. no es nulo}) \end{array} \right. \end{align*}$$

Cuasicamino de flujo aumentable desde $F$ a $S$. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en $R_{FS}$, prestaremos especial atención a los cuasicaminos de flujo aumentable que van desde la fuente $F$ hasta el sumidero $S$. Estos se denotan como $\pi_{FS}$.

Holgura de un arco. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en $R_{FS}$ y $\pi_{FS}$ cuasicamino de flujo aumentable desde $F$ a $S$ en $R_{FS}$. Se define la holgura de $e \in \pi_{FS}$ como:

$$\begin{align*} \Delta_e = \left\{ \begin{array}{ll} p_e - f_e & \forall \text{ arco positivo } e \in \pi_{FS}\\ f_e & \forall \text{ arco negativo } e \in \pi_{FS} \end{array} \right.\\ \end{align*}$$

Holgura de un cuasicamino de flujo aumentable. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en $R_{FS}$ y $\pi_{FS}$ cuasicamino de flujo aumentable desde $F$ a $S$ en $R_{FS}$. Se define la holgura de $\pi_{FS}$ como:

$$\begin{align*} \Delta_{\pi_{FS}} = \min_{e \in \pi_{FS}} \{\Delta_e\}\\ \end{align*}$$

Proposición 4.1

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en $R_{FS}$ y $\pi_{FS}$ cuasicamino de flujo aumentable desde $F$ a $S$ en $R_{FS}$ tal que la holgura mínima de sus arcos es $\Delta_{\pi_{FS}}$. Si se considera la aplicación:

$$\begin{align*} \widehat{f} : A & \longrightarrow \mathbb{R}^{ + }\\ e & \longmapsto \widehat{f_e} = \left\{ \begin{array}{ll} f_e + \Delta_{\pi_{FS}} & \text{si } e \text{ es arco positivo en } \pi_{FS}\\ f_e - \Delta_{\pi_{FS}} & \text{si } e \text{ es arco negativo en } \pi_{FS}\\ f_e & \text{si } e \notin \pi_{FS} \end{array} \right. \end{align*}$$

entonces la colección $\widehat{f} = \{\widehat{f_e}: e \in A\}$ es un flujo en $R_{FS}$ con valor $v_{\widehat{f}} = v_f + \Delta_{\pi_{FS}}$.

Corte en una red. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $\{B, B^c\}$ partición de $V$ tal que $F \in B$ y $S \in B^c$ (separa el vértice fuente del sumidero). Al subconjunto de arcos formado por los arcos con origen en $B$ y destino en $B^c$ se le denomina corte y se denota como:

$$\begin{align*} \delta^{ + }(B) = \{(i, j) \in A: i \in B, j \in B^c\} \end{align*}$$

Análogamente, podemos definir el conjunto inverso que no cumple las condiciones de corte dado por:

$$\begin{align*} \delta^{ - }(B) = \{(i, j) \in A: i \in B^c, j \in B\}\\ \end{align*}$$

Conjunto de cortes en una red. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, se define el conjunto de cortes en $R_{FS}$ como:

$$\begin{align*} \mathcal{D}^{ + } = \{\delta^{ + }(B): B \subseteq V, F \in B, S \in B^c\} \end{align*}$$

Capacidad de un corte. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f = \{f_{ij}: (i, j) \in A\}$ flujo y $\delta^{ + }(B)$ corte de dicha red, se define la capacidad del corte $\delta^{ + }(B)$ como la suma de las capacidades de los arcos que forman el corte:

$$\begin{align*} p(\delta^{ + }(B)) = \displaystyle \sum_{(i, j) \in \delta^{ + }(B)} p_{ij} = \displaystyle \sum_{i \in B, j\in B^c \cap \Gamma(i)} p_{ij}\\ \end{align*}$$

Flujo neto a través de un corte. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f = \{f_{ij}: (i, j) \in A\}$ flujo y $\delta^{ + }(B)$ corte de dicha red, se define el flujo neto a través del corte $\delta^{ + }(B)$ como:

$$\begin{align*} f(\delta^{ + }(B)) = \displaystyle \sum_{(i, j) \in \delta^{ + }(B)} f_{ij} - \displaystyle \sum_{(i, j) \in \delta^{ + }(B^c)} f_{ij} = \displaystyle \sum_{i \in B, j\in B^c \cap \Gamma(i)} f_{ij} - \displaystyle \sum_{i \in B^c, j\in B \cap \Gamma(i)} f_{ij}\\ \end{align*}$$

Proposición 4.2

Sea $R_{FS} = (V, A, p)$ red estándar, $f = \{f_{ij}: (i, j) \in A\}$ flujo en $R_{FS}$ y $\delta^{ + }(B)$ corte de dicha red. Entonces, el flujo neto a través del corte es igual al valor del flujo, es decir:

$$\begin{align*} v_f = f(\delta^{ + }(B))\\ \end{align*}$$

Proposición 4.3

Sea $R_{FS} = (V, A, p)$ red estándar, $f = \{f_{ij}: (i, j) \in A\}$ flujo en $R_{FS}$ y $\delta^{ + }(B)$ corte de dicha red, se verifican:

1. El valor del flujo $f$ está acotado superiormente por la capacidad del corte, es decir:

$$\begin{align*} v_f \leq p(\delta^{ + }(B)) \end{align*}$$

2. Además, se cumple que:

$$\begin{align*} v_f = p(\delta^{ + }(B)) \iff \left\{ \begin{array}{ll} f_{ij} = p_{ij} & \forall (i, j) \in \delta^{ + }(B)\\ f_{ij} = 0 & \forall (i, j) \in \delta^{ + }(B^c) \end{array} \right. \end{align*}$$

Corte mínimo en una red. Definición

Sea $R_{FS} = (V, A, p)$ red estándar y $\delta^{ + }(B)$ un corte, se dice que es corte mínimo si:

$$\begin{align*} p(\delta^{ + }(B)) \leq p(\delta^{ + }(D)) \qquad \forall \delta^{ + }(D) \in \mathcal{D}^{ + }\\ \end{align*}$$

Flujo máximo en una red. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, se dice que un flujo $f$ en $R_{FS}$ es flujo máximo si:

$$\begin{align*} v_f \geq v_g \qquad \forall g \text{ flujo en } R_{FS}\\ \end{align*}$$

Corolario 4.4

Sea $R_{FS} = (V, A, p)$ red estándar, si $\delta^{ + }(B)$ y $f$ son un corte y un flujo en $R_{FS}$ respectivamente, tales que:

$$\begin{align*} v_f = p(\delta^{ + }(B)) \implies f \text{ es flujo máximo y } \delta^{ + }(B) \text{ es corte mínimo}\\ \end{align*}$$

Teorema 4.5

Sea $R_{FS} = (V, A, p)$ red estándar y $f$ flujo en $R_{FS}$. Entonces se cumplen:

$$\begin{align*} f \text{ flujo máximo} \iff \nexists \pi_{FS} \text{ cuasicamino de flujo aumentable desde } F \text{ a } S \text{ en } R_{FS}\\ \end{align*}$$

Algoritmo de Ford-Fulkerson

El objetivo de este algoritmo es encontrar un flujo máximo $f$, para ello, la idea es ir saturando cuasicaminos de flujo aumentable hasta que no queden más. Sea $R_{FS} = (V, A, p)$ red estándar, el algoritmo es el siguiente:

1. Sea el flujo $f$ definido como $f_e = 0$ para todo $e \in A$.

2. Etiquetado:

3. Para el cuasicamino $f$-aumentable $\pi_{FS}$ formado por los arcos entre vértices etiquetados, obtener $\Delta_{\pi_{FS}}$ y con ese valor, obtener el nuevo flujo $\widehat{f}$ según la proposición 4.1.

4. Volver al paso 2 borrando todas las etiquetas.

Porposición 4.6

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo máximo y $\delta^{ + }(B)$ corte mínimo, entonces:

$$\begin{align*} v_f = p(\delta^{ + }(B))\\ \end{align*}$$

Corolario 4.7

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo y $\delta^{ + }(B)$ corte de dicha red. Son equivalentes:

1. $f$ es flujo máximo y $\delta^{ + }(B)$ es corte mínimo.
2. $v_f = p(\delta^{ + }(B))$.
3. Todo arco de $\delta^ + (B)$ es saturado y todo arco de $\delta^ + (B^c)$ es libre

Consecuencias del teorema de Ford-Fulkerson

A partir del algoritmo de Ford-Fulkerson no solo obtenemos un flujo máximo, si no que también podemos obtener el corte mínimo. Este último es generado por todos los vértices etiquetados en la última iteración, es decir, los vértices alcanzables desde $F$ mediante cuasicaminos de flujo aumentable.

Flujo de costo mínimo

El objetivo del flujo de coste mínimo es determinar los flujos en los diferentes arcos que minimicen el coste total del flujo de la red y, simultáneamente, conservan el flujo y satisfacen las capacidades de los arcos.

Coste del flujo. Definición

Sea $R_{FS} = (V, A, p, c)$ una red estándar con función de costes $c : A \to \mathbb{R}$. El coste total asociado a un flujo $f$ en la red $R_{FS}$ viene dado por:

$$\begin{align*} c_f = \displaystyle \sum_{(i, j) \in A} c_{ij} f_{ij}\\ \end{align*}$$

Coste mínimo. Definición

Sea $R_{FS} = (V, A, p, c)$ una red estándar con función de costes $c : A \to \mathbb{R}$. Un flujo $f$ en la red $R_{FS}$ es un flujo de coste mínimo si:

$$\begin{align*} c_f = \min_{f \in \mathcal{F}_v(R_{FS})} c_f \end{align*}$$

donde $\mathcal{F}_v(R_{FS}) = \left\{f : f \text{ es flujo de valor } v \text{ en } R_{FS}\right\}$.

Cuasicircuito. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, un cuasicircuito es un cuasicamino en el que el primer y último vértice coinciden.

Cuasicircuito $f$-aumentable. Definición

Sea $R_{FS} = (V, A, p)$ red estándar y $f$ flujo en dicha red. Un cuasicircuito es $f$-aumentable si todo arco positivo no está saturado y todo arco negativo no es libre.

Holgura del cuasicircuito. Definición

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en dicha red y $\phi$ un cuasicircuito $f$-aumentable. La holgura del cuasicircuito $\phi$ viene dada por:

$$\begin{align*} \Delta = \min_{e \in \phi} \Delta_e\\ \end{align*}$$

Proposición 4.8

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo en dicha red y $\phi$ cuasicircuito $f$-aumentable tal que la holgura mínima de sus arcos es $\Delta_\phi$, si consideramos la aplicación:

$$\begin{align*} \widehat{f_{ij}} = \begin{cases} f_{ij} + \Delta_\phi & \text{si } (i, j) \in \phi \text{ es arco positivo}\\ f_{ij} - \Delta_\phi & \text{si } (i, j) \in \phi \text{ es arco negativo}\\ f_{ij} & \text{en otro caso} \end{cases} \end{align*}$$

se tiene que la colección $\widehat{f} = \{\widehat{f_{ij}} : (i, j) \in A\}$ es un flujo en la red $R_{FS}$ con el mismo valor que $f$.

Red asociada al flujo. Definición

Sea $R_{FS} = (V, A, p)$ red estándar y $f$ un flujo en dicha red, se define la red asociada al flujo $f$ como la red $R_f = (V, A_f, p)$ con:

$$\begin{align*} A_f = \left\{(i, j) : (i, j) \in A \lor (j, i) \in A \text{ con } u_{ij} > 0\right\} \end{align*}$$

donde definimos $u_{ij}$ como:

$$\begin{align*} u_{ij} = \begin{cases} p_{ij} - f_{ij} & \text{si } (i, j) \in A\\ f_{ji} & \text{si } (j, i) \in A \end{cases} \end{align*}$$

Proposición 4.9

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ flujo y $R_f = (V, A_f, p)$ red asociada al flujo $f$, se cumple que:

$$\begin{align*} \phi \text{ cuasicircuito } f\text{-aumentable en } R_{FS} \iff \text{arcos de } \phi \text{ generan circuito elemental } \beta\\ \end{align*}$$

Selección de circuitos elementales de $R_f$. Idea

Intuitivamente buscamos cuasicircuitos de flujo aumentable que reduzcan el coste del flujo. Podemos notar que si el cuasicircuito de flujo aumentable $\phi$ verifica que:

$$\begin{align*} \displaystyle \sum_{e \text{ pos}} c_e - \displaystyle \sum_{e \text{ neg}} c_e < 0 \end{align*}$$

entonces el coste del nuevo flujo es menor (veremos que esto es cierto en general).

Red residual. Definición

Sea $R_{FS} = (V, A, p, c)$ red estándar y $f$ flujo en dicha red, se define la red residual asociada al flujo $f$ como la red $R_f = (V, A_f, u, r)$ donde:

$$\begin{align*} A_f = \left\{(i, j) : (i, j) \in A \lor (j, i) \in A \text{ con } u_{ij} > 0\right\} \end{align*}$$

donde se definen:

$$\begin{align*} u_{ij} = \begin{cases} p_{ij} - f_{ij} & \text{si } (i, j) \in A\\ f_{ji} & \text{si } (j, i) \in A \end{cases}\qquad \text{y} \qquad r_{ij} = \begin{cases} c_{ij} & \text{si } (i, j) \in A\\ -c_{ji} & \text{si } (j, i) \in A \end{cases} \end{align*}$$

Proposición 4.10

Sea $R_{FS} = (V, A, p, c)$ red estándar, $f$ flujo en dicha red, $\phi$ cuasicircuito $f$-aumentable y $\beta$ el circuito elemental generado por los arcos de $\phi$ en la red residual $R_f$. Si consideramos el flujo $\hat{f}$ definido en la proposición 4.8, entonces:

$$\begin{align*} c_{\hat{f}} = c_f + \Delta_\phi \cdot \displaystyle \sum_{e \in \beta} r_e\\ \end{align*}$$

Corolario 4.11

Sea $f$ flujo de valor $v_f$ en la red estándar $R_{FS} = (V, A, p, c)$. Si $f$ es un flujo de coste mínimo, entonces no existe ningún circuito elemental $\beta$ en $R_f$ con:

$$\begin{align*} \displaystyle \sum_{e \in \beta} r_e < 0\\ \end{align*}$$

Red de pesos asociada a una red estándar. Definición

Sea $R_{FS} = (V, A, p)$ red estándar y $f, f^*$ dos flujos en dicha red con $v_{f} = v_{f^*}$, se define la red de pesos $R_{ff^*} = (V, A_{ff^*}, f^* - f)$ tal que:

• Tiene los mismos vértices que $R_{FS}$.
• Los arcos son:

$$\begin{align*} A_{ff^*} = \left\{(i, j) : (i, j) \in A \text{ con } f_{ij} < f^*_{ij} \lor (j, i) \in A \text{ con } f_{ji} > f^*_{ji}\right\} \end{align*}$$

es decir, están los mismos arcos que en $A$ si su flujo en $f^*$ es mayor que en $f$ y los arcos que están en sentido contrario si su flujo en $f^*$ es menor que en $f$.

• El peso de cualquier arco $(i, j) \in A_{ff^*}$ es:

$$\begin{align*} (f^* - f)_{ij} = \begin{cases} f^*_{ij} - f_{ij} & \text{si } (i, j) \in A \text{ con } f_{ij} < f^*_{ij}\\ f_{ji} - f^*_{ji} & \text{si } (j, i) \in A \text{ con } f_{ji} > f^*_{ji} \end{cases} \end{align*}$$

Lema 4.12

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ y $f^*$ dos flujos diferentes con $v_f = v_{f^*}$ y $R_{ff^*} = (V, A_{ff^*}, f^* - f)$ entonces:

$$\begin{align*} \displaystyle \sum_{j: (i, j) \in A_{ff^*}} (f^* - f)_{ij} = \displaystyle \sum_{j: (j, i) \in A_{ff^*}} (f^* - f)_{ji} \quad \forall i \in V\\ \end{align*}$$

Lema 4.13

Sea $R_{FS} = (V, A, p)$ red estándar, $f$ y $f^*$ dos flujos diferentes con $v_f = v_{f^*}$ entonces existe una colección $r$ de circuitos $\mathcal{B} = \{\beta_1, \dots , \beta_r\}$ en la red de pesos $R_{ff^*}$ con $r \leq |A|$ tales que:

$$\begin{align*} (f^* - f)_{ij} = \displaystyle \sum_{\beta_k \in \mathcal{B}: (i, j) \in \beta_k} \Lambda_{\beta_k} \quad \forall (i, j) \in A_{ff^*} \end{align*}$$

donde $\Lambda_{\beta_k} = \displaystyle \min_{(i, j) \in \beta_k} (f^* - f)_{ij}$.

Teorema 4.14

Sea $f$ flujo de valor $v_f$ en la red estándar $R_{FS} = (V, A, p, c)$. Si no existe ningún circuito elemental $\beta$ en $R_f$ con:

$$\begin{align*} \displaystyle \sum_{e \in \beta} r_e < 0 \end{align*}$$

entonces $f$ es un flujo de coste mínimo en $R_{FS}$.

Corolario 4.15

Un flujo $f$ de valor $v_f$ en una red estándar con costes $R_{FS} = (V, A, p, c)$ es un flujo de coste mínimo si y solo si no existe ningún circuito elemental $\beta$ en $R_f$ con:

$$\begin{align*} \displaystyle \sum_{e \in \beta} r_e < 0\\ \end{align*}$$

Algoritmo de Klein

El objetivo del algoritmo es encontrar un flujo $f$ de manera que cualquier otro flujo $f^*$ con $v_f = v_{f^*}$ se tiene que cumplir que $c_f \leq c_{f^*}$. El algoritmo es el siguiente:

1. Hacer $t = 0$ y asignar $f^0 > 0$ de valor $v$ a la red $R_{FS} = (V, A, p, c)$.
2. Construir la red residual $R_{f^t} = (V, A_{f^t}, u, r)$ asociada a $R_{FS}$ y al flujo $f^t$.
3. Buscar en $R_{f^t}$ un circuito elemental $\beta_t$ con:

$$\begin{align*} \displaystyle \sum_{e \in \beta_t} r_e < 0 \end{align*}$$

Si existe ir al paso 4, si no $f^t$ es flujo de valor $v$ y coste mínimo $c_{f^t}$ 4. Calcular $\Delta_t = \min_{(i, j) \in \beta_t} u_{ij}$ y definir el flujo $f^{t + 1}$ como:

$$\begin{align*} f_{ij}^{t + 1} = \begin{cases} f_{ij}^t + \Delta_t & \text{si } (i, j) \in \phi_t \text{ es arco positivo}\\ f_{ij}^t - \Delta_t & \text{si } (i, j) \in \phi_t \text{ es arco negativo}\\ f_{ij}^t & \text{en otro caso} \end{cases} \end{align*}$$

donde $\phi_t$ es el cuasicircuito en $R_{FS}$ asociado a $\beta_t$. Hacer $t = t + 1$ y volver al paso 2.