2026/09/30 Online Opt Scribe
$\newcommand{R}{\mathbb{R}}$
Linear Programming
$$\max_{f, F} F$$ subject to $$\sum_{e\in \text{OUT}(v)}f_e - \sum_{e\in \text{IN}(v)}f_e = \begin{cases} F, v = s \ -F, v = t \ 0, v \ne s, t \end{cases}$$ and $$0 \le f_e \le c_e, \forall e \in E$$
To decipher this we first need to understand what each function means.
This is the Maximum Flow Problem stated mathematically. Suppose we have some network $N$ which is a pair of vertices and edges $(V, E)$ where $E \subseteq V\times V$
Let us define Capacity as a function $c: E \rightarrow \R^+$. Then we can denote the capacity of an edge $c_e = c_{uv} = c(e)$.
We define flow as a funciton $f: E \rightarrow \R^+$. Naturally, we can see that $f_e \le c_e, \forall e\in E$
It is also easy to see that flow must be conserved.
For any node $v$ other than the source $s$ or the sink $t$, we have
$$\sum_{u} f_{uv} - \sum_{u} f_{vu} = 0$$
How do we route flows from the source to the sink to achieve the maximum $F$?
We can express this in a more succint way using matrices. Suppose we have an adjacency matrix $B$ where the element $B_{ij} = 1$ if there exists an edge between vertex $i$ and $j$.
$$Bf = Fb$$
where $f$ is a column vector whose entries are $f_e$s
As you might remember from [[