Question

Consider the following generalization of the maximum flow problem.

You are given a directed network $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$with edge capacities $\mathbf{\left\{}{\mathbf{c}}_{\mathbf{e}}\mathbf{\right\}}$. Instead of a single $\mathbf{(}\mathbf{s}\mathbf{,}\mathbf{t}\mathbf{)}$pair, you are given multiple pairs $\mathbf{(}{\mathbf{s}}_1\mathbf{,}{\mathbf{t}}_1\mathbf{)}\mathbf{,}\mathbf{(}{\mathbf{s}}_2\mathbf{,}{\mathbf{t}}_2\mathbf{)}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{(}{\mathbf{s}}_k\mathbf{,}{\mathbf{t}}_k\mathbf{)}$, where the ${\mathbf{s}}_{\mathbf{i}}$are sources of $\mathbf{G}$and ${\mathbf{t}}_{\mathbf{i}}$the are sinks of $\mathbf{G}$. You are also given $\mathbf{k}$demands ${\mathbf{d}}_1\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{d}}_k$. The goal is to find $\mathbf{k}$flows ${\mathbf{f}}^{\mathbf{\left(}\mathbf{1}\mathbf{\right)}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{f}}^{\mathbf{\left(}\mathbf{k}\mathbf{\right)}}$with the following properties:

• ${\mathbf{f}}^{\mathbf{\left(}\mathbf{i}\mathbf{\right)}}$is a valid flow from${\mathbf{S}}_{\mathbf{i}}$ to${\mathbf{t}}_i$ .
• For each edge $\mathit{e}$, the total flow${\mathbf{f}}_e^{\mathbf{\left(}\mathbf{1}\mathbf{\right)}}\mathbf{+}{\mathbf{f}}_e^{\mathbf{\left(}\mathbf{2}\mathbf{\right)}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathbf{f}}_e^{\mathbf{\left(}\mathbf{k}\mathbf{\right)}}$ does not exceed the capacity${\mathbf{c}}_e$ .
• The size of each flow${\mathbf{f}}^{\left(\mathbf{i}\right)}$ is at least the demand ${\mathbf{d}}_i$.
• The size of the total flow (the sum of the flows) is as large as possible.

How would you solve this problem?

Short answer

The problem is solved by the linear program for max flow as follows:

Maximize the flow of the network:

$\max \sum _{\mathrm{i}=1}^{\mathrm{k}}\sum _{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})\mathrm{ÎE}}{\mathrm{f}}_{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})}^{\left(\mathrm{i}\right)}$

Compare the flow :

$\forall \mathrm{e}\in \mathrm{E}:{\mathrm{f}}_{\mathrm{e}}^{\left(1\right)}+{\mathrm{f}}_{\mathrm{e}}^{\left(2\right)}+\dots {\mathrm{f}}_{\mathrm{e}}^{\left(\mathrm{i}\right)}\le {\mathrm{c}}_{\mathrm{e}}$

$\forall \mathrm{v}\in \mathrm{V}:\sum _{\mathrm{uv}\in \mathrm{E}}{\mathrm{f}}_{\mathrm{uv}}^{\left(\mathrm{i}\right)}=\sum _{\mathrm{uw}\in \mathrm{E}}{\mathrm{f}}_{\mathrm{uw}}^{\left(\mathrm{i}\right)}$

$\begin{array}{l}{\mathrm{f}}^{\left(\mathrm{i}\right)}=\sum _{(\mathrm{u},\mathrm{t})\in \mathrm{E}}{\mathrm{f}}_{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})}^{\left(\mathrm{i}\right)}\ge {\mathrm{d}}_{\mathrm{i}}\\ {\mathrm{f}}_{\mathrm{e}}^{\left(\mathrm{i}\right)}\ge 0\end{array}$

Step-by-step solution

Explain the demands in the given problem

The generalization of the maximum flow problem considers the directed network with the edge capacities $\left\{{\mathrm{c}}_{\mathrm{e}}\right\}$. Multiple pairs of sources and sinks are given. There is a demand$d_1,\dots ,d_k$ for each flow.

The maximum flow aims to send as much data as possible from source to sink without exceeding the edge weights.

Give the solution to determine the maximum flow problem.

The maximum flow with the demands and to maximize the flow the solution is found by the linear program as follows.

Maximize the flow of the network:

$\max \sum _{\mathrm{i}=1}^{\mathrm{k}}\sum _{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})\in \mathrm{E}}{\mathrm{f}}_{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})}^{\left(\mathrm{i}\right)}$

Compare the flow with the edge capacity, that the total flow does not exceed the edge capacity.

$\forall \mathrm{e}\in \mathrm{E}:{\mathrm{f}}_{\mathrm{e}}^{\left(1\right)}+{\mathrm{f}}_{\mathrm{e}}^{\left(2\right)}+\dots {\mathrm{f}}_{\mathrm{e}}^{\left(\mathrm{i}\right)}\le {\mathrm{c}}_{\mathrm{e}}$

The number of the entering and the leaving edges are equal.

$\forall \mathrm{v}\in \mathrm{V}:\sum _{\mathrm{uv}\in \mathrm{E}}{\mathrm{f}}_{\mathrm{uv}}^{\left(\mathrm{i}\right)}=\sum _{\mathrm{uw}\in \mathrm{E}}{\mathrm{f}}_{\mathrm{uw}}^{\left(\mathrm{i}\right)}$

The size of the flow is at least the demand.

$\begin{array}{l}{\mathrm{f}}^{\left(\mathrm{i}\right)}=\sum _{(\mathrm{u},\mathrm{t})\in \mathrm{E}}{\mathrm{f}}_{(\mathrm{u},{\mathrm{t}}_{\mathrm{i}})}^{\left(\mathrm{i}\right)}\ge {\mathrm{d}}_{\mathrm{i}}\\ {\mathrm{f}}_{\mathrm{e}}^{\left(\mathrm{i}\right)}\ge 0\end{array}$

The size of the total flow is greater than zero.

Therefore, the problem is solved by the linear program for max flow.