Min-Cost Flow: LP Formulation

In a min-cost flow problem, we have a directed network $G=(V,E)$ in which each arc $(i,j)$ has a capacity $u_{ij}\ge 0$ and a per-unit shipping cost $c_{ij}$. We must ship $d$ units of flow from a source $s$ to a sink $t$ as cheaply as possible.

We model this as a linear program. The decision variable on each arc is

$$x_{ij} = \text{units of flow sent along arc } (i,j).$$

The objective minimizes the total shipping cost:

$$\min \sum_{(i,j)\in E} c_{ij}\, x_{ij}.$$

Each flow variable must respect the arc's capacity bound:

$$0 \le x_{ij} \le u_{ij}\quad\text{for every arc } (i,j)\in E.$$

The lower bound $0$ enforces that flow only moves in the arc's stated direction.

For example, suppose the network has three arcs with the following data:

$$\begin{array}{c|cc} \text{Arc} & c_{ij} & u_{ij} \\ \hline (s,a) & 2 & 3 \\ (s,t) & 5 & 2 \\ (a,t) & 1 & 4 \end{array}$$

The objective and the capacity bounds of the LP are

$$\min\; 2x_{sa} + 5x_{st} + x_{at},$$ $$0\le x_{sa}\le 3,\quad 0\le x_{st}\le 2,\quad 0\le x_{at}\le 4.$$

We still need flow-conservation constraints, which we'll add shortly.