# Minimum Cost Network Flow Network flow models are one specific format of mathematical programs. These are used to study operations that are related to network transportation. A unified model, called Minimum Cost Network Flow (MCNF) covers many network operations. MCNF is a special form of linear program or integer program.

Even better, MCNF has a very nice property: once you formulate the problem, set all the variables to be integer, and solve it, you will always get an integer solution directly by using the linear programming relaxation.

## Definition of Network Flow

Cosider a weighted, capacitated network `G = (V, E)`, where G is the network, V is the set of node, and E is the set of arcs. For node `i ∈ V`, there is a supply quantity `bi`.

Total supplies equal total demands `Σi∈V bi = 0`. For an arc `(i, j) ∈ E`, the value `uij` is the upper bound of the flow size (capacity), and the weight `cij` is the cost of the arc. Then the problem is: “how do we makeup a shipping plan from the supply nodes to the demand nodes, with minimum cost? “

Obviously, to formulate the problem, for all `(i, j) ∈ E`, the flow size of an arc `(i, j)` are the decision variables `xij` that we care about, for each of them there are constraints: `0 ≤ xij ≤ uij`. The object function would be to minimize the total cost: `min Σ cij xij`.

Besides the usual decision variables, constraints and objective function, there are more constraints called flow balancing / conservation that we need to consider, which ensures that all the demands are satisfied. The total supplies equal to the total demands is required for feasibility.

Since we did not set constraints that `xij` are integers, the formulation is actually a linear program. The beauty of MCNF is that we get integer solution for free, I mean there is no more effort than solving a linear program, as long as:

1. Supply quantities `bi` are all integers
2. Upper bounds `uij` are all integers.

To understand why, we need to first learn a concept called Total Unimodularity.

### Total Unimodularity

A square matrix is unimodular if its determinant is 1 or -1. A matrix is totally unimodular (TU) if all of its square sub-matrices are either singular (determinant = 0) or unimodular (determinant = 1 or -1).

For a standard form of linear programs `min {cT x | A x = b, x ≥ 0}`, if A is total unimodular and b are all integers, `b ∈ Zm`, then any optimal basic feasible solution `x*` obtained by the simplex method must satisfy `x* ∈ Zn`.

However, what are the sufficient conditions for total unimodularity? For a matrix, if:

1. All its elemets are either 1, 0 or -1,
2. Each column of the matrix contains at most two nonzero elements, AND
3. Rows of the matrix can be divided into two groups so that for each column two nonzero elements are
• in the same group if and only if they are different.
• not in the same group if and only if they are the same.

Than the matrix is totally unimodular, if `uij = ∞`, i.e. there is no constraints on `xij`.

However, if there is constraints on `xij`, i.e. `uij < ∞`, some more arguments are needed. But still for any MCNF problem that is feasible, the simplex method (or any other method) will give you an integer optimal solution directly.

## Special Network Flow Models

There are many well-known problems that can be formulated as special cases of the MCNF models. Then it will be easy to find the final optimal solution using the general simplex method, without worrying about spending more time and designing some special algorithms.

### Transportation Problems

A firm owns `n` factories that supply one product to `m` markets. The capacity of factory i is `si, i = 1...n`. The demand of market j is `dj, j = 1...m`. Between factory i and j, there is a route, the unit cost for shipping one unit from factory i to market j is `cij`. Then the problem is “how to ship the product to fulfill all demands while minimizing the total costs?”

Obviously this is a special case of MCNF by considering:

1. Factories as supply nodes, whose supply quantity is `si`
2. Markets as demand nodes, whose demand quantity is `-dj`
3. No transshipment nodes
4. Arc weights are the unit transportation cost `cij`
5. No limitations or constraints for arc, i.e. `uij = ∞`
6. Also `Σni=1 si = Σmj=1 dj`
7. Let `xij` be the shipping quantity on arc `(i, j)`

Possible variants of the problem include:

Let I and J be the sets of factories and markets:

``````min Σi∈I Σj∈J cij xij
s.t. Σmj=1 xij = si ∀i ∈ I
Σni=1 xij = dj ∀j ∈ J

xij ∈ Z+     ∀i ∈ I, ∀j ∈ J``````

#### Assignment Problems

A manager is assigning n jobs to n workers. The assignment must be one-to-one, the cost for worker j to complete job i is `cij`. Obviously, this problem is a special case of the transportation problem. Jobs are factories and workers are markets.

What if there are fewer jobs than workers? All you need to do is to create virtual jobs with cost zero. The problem requires you to have equal number of jobs and workers.

Let I and J be the sets of jobs and workers:

``````min Σi∈I Σj∈J cij xij
s.t. Σnj=1 xij = 1 ∀i ∈ I
Σni=1 xij = 1 ∀j ∈ J

xij ∈ {0, 1}     ∀i ∈ I, ∀j ∈ J``````

#### Transshipment Problems

If there are transshipment nodes in a transportation problem, the problem is called a transshipment problem. Transshipment problem is a superset of transportation problem in the sense that `bi` can be zero.

``````MCNF
↓ if uij = ∞
Transshipment
↓ if bi ≠ 0
Transportation
↓ if bi = 1 or -1
Assignment``````

### Shortest Path Problems

For a given network, each arc has a weight `dij ≥ 0` as a distance, then “what is the shortest path to go from a given node `s` to a given node `t`? A shortest path problem can be formulated as an MCNF problem:

1. supply node is `s` with supply quantity 1
2. demand node is `t`with demand quantity -1
3. all other nodes are transshipment nodes

Let T be the set of transshipment nodes:

``````min Σi∈I Σj∈J dij xij
s.t. Σ(s,j)∈E xsj = 1
Σ(i,t)∈E xit = 1
Σ(i,k)∈E xik - Σ(k,j)∈E xkj = 0   ∀k ∈ T

xij ∈ {0, 1}     ∀(i,j) ∈ E``````

Shortest path problems is a special case of transshipment problems:

``````Transshipment
↓ if bs = 1, bt = -1, bi = 0   ∀i ∈ T
Shortest Path``````

### Maximum Flow Problems

For a network, each arc has a capacity (instead of a cost), the problem is “how many units may we send from a given node `s` to a given node `t`?” We want to send as many units as possible. Now this is a maximum flow problem from `s` to `t`, instead of a minimum problem.

We can imagine a new arc from `t` back to `s`, now formulating a maximum flow problem from `s` to `t` is equivalently to try to send some virtual units from `t` back to `s`, but with some rewards by paying some negative costs.

1. The original arcs’ costs are 0, with some limited capacities.
2. The new imaginary arc’s cost is -1, with unlimited capacity.

What we should do is to try to push as much as possible from `s` to `t` so that when they go back from `t` to `s` we are able to earn as much reward as possible.

Let T be the set of transshipment nodes, let `xts` be the flow size of the new imaginary arc `(t, s)`, and its cost is `cts = -1`:

``````min -xts
s.t. Σ(i,k)∈E xik - Σ(k,j)∈E xkj = 0   ∀k ∈ T

xij ≤ uij        ∀(i,j) ∈ E
xij ∈ Z+        ∀(i,j) ∈ E``````

Max flow problems is a special case of MCNF problems:

``````MCNF
↓ if cts = -1, cij = 0   ∀(i,j) ∈ E
Max Flow``````

## My Certificate

For more on Minimum Cost Network Flow, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-theory

## Related Quick Recap

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

All of your support will be used for maintenance of this site and more great content. I am humbled and grateful for your generosity. Thank you!

 Your generosity and kindness is overwhelming!Donate \$1.99 - Good job!Donate \$4.99 - Keep it up!Donate \$14.99 - Very helpful!Donate \$29.99 - Looking forward to more! 