Transportation and Assignment Problems as Min-Cost Flow

Formulates the classical transportation problem and the assignment problem as instances of min-cost flow on a bipartite network with a source and sink, and solves small instances by computing total cost or enumerating assignments.

Step 1 of 157%

Tutorial

The Transportation Problem as Min-Cost Flow

The transportation problem asks how to ship a single commodity from $m$ supply nodes to $n$ demand nodes at minimum total cost. Supplier $i$ has $s_i$ units available, customer $j$ requires $d_j$ units, and shipping one unit from $i$ to $j$ costs $c_{ij}$ .

We model this as a min-cost flow problem on a bipartite network with an added source $S$ and sink $T$ . The arcs are:

$(S, i)$ with capacity $s_i$ and cost $0$ , for each supplier $i$ .
$(i, j)$ with capacity $\infty$ and cost $c_{ij}$ , for each supplier-customer pair.
$(j, T)$ with capacity $d_j$ and cost $0$ , for each customer $j$ .

Assuming the problem is balanced, meaning

\sum_{i=1}^m s_i = \sum_{j=1}^n d_j,

the optimal shipment is a min-cost flow from $S$ to $T$ of value

F = \sum_{i=1}^m s_i.

The total arc count is $m + mn + n$ . For example, with $m = 2$ suppliers and $n = 2$ customers, the network has $2 + 4 + 2 = 8$ arcs.