Maximum Flow Optimization

We have a network (represented as directed graph). The graph has a “Source” of a medium (it can be for example gas, water, or electricity) and Sink with additional nodes in between. All edges between source and sink has defined maximal capacity.

graph LR;
    A["Source"];
		D["Sink"];
		A-->|"10"|B1;
    A-->|"8"|B2;
    B1-->|"6"|C1;
		B1-->|"2"|C2;
		B2-->|"4"|C1;
		B2-->|"5"|C2;
		C1-->|"8"|D;
		C2-->|"9"|D;

What is the maximum amount medium we can transmit through the sink?

Mathematical Model

Let us first define our optimization variables $x_i$ as individual flows through the edges of our graph

graph LR;
    A["Source"];
		D["Sink"];
		A--->|"x₀ ≤ 10"|B1;
    A--->|"x₁ ≤ 8"|B2;
    B1-->|"x₂ ≤ 6"|C1;
		B1-->|"x₃ ≤ 2"|C2;
		B2-->|"x₄ ≤ 4"|C1;
		B2-->|"x₅ ≤ 5"|C2;
		C1-->|"x₆ ≤ 8"|D;
		C2-->|"x₇ ≤ 9"|D;

we may then write the problem as

$$\begin{array}{rl}\underset{x}{\max }& x_6+x_7\\ \text{s.t.}& 0\le x\le u\\ & x_0=x_2+x_3\\ & x_1=x_4+x_5\\ & x_2+x_4=x_6\\ & x_3+x_5=x_7\end{array}$$ where $$u^{\top }=\left[\begin{array}{cccccccc}10& 8& 6& 2& 4& 5& 8& 9\end{array}\right]$$

Canonical Form

Manipulating the objective into the canonical form can be done simply with $$c^{\top }=\left[\begin{array}{cccccccc}0& 0& 0& 0& 0& 0& 1& 1\end{array}\right].$$ To deal with the constraints let us first formulate the equality constraints in matrix form as: $$A_{\mathrm{eq}}x=0$$ where $$A_{\mathrm{eq}}=\left[\begin{array}{cccccccc}-1& 0& 1& 1& 0& 0& 0& 0\\ 0& -1& 0& 0& 1& 1& 0& 0\\ 0& 0& -1& 0& -1& 0& 1& 0\\ 0& 0& 0& -1& 0& -1& 0& 1\end{array}\right].$$ Equivalently we may write it as $$0\le A_{\mathrm{eq}}x\le 0.$$ Together with the upper bounds they can be now rewritten into the canonical form $$\underset{A}{\underbrace{\left[\begin{array}{c}I\\ A_{\mathrm{eq}}\\ -A_{\mathrm{eq}}\end{array}\right]}}x\le \underset{b}{\underbrace{\left[\begin{array}{c}u\\ 0\\ 0\end{array}\right]}}$$