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 `b`

._{i}

The node `i` is a | |

`b` | supply node, say factory |

`b` | demand node, say marketplace |

`b` | transshipment node |

Total supplies equal total demands `Σ`

. For an arc _{i∈V} b_{i} = 0`(i, j) ∈ E`

, the value `u`

is the upper bound of the flow size (capacity), and the weight _{ij}`c`

is the cost of the arc. Then the problem is: “how do we makeup a shipping plan from the _{ij}**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 `x`

that we care about, for each of them there are constraints: _{ij}`0 ≤ x`

. The object function would be to minimize the total cost: _{ij} ≤ u_{ij}`min Σ c`

._{ij} x_{ij}

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.

Supply node | Sum of all outgoing `x` = its supply quantity `b` . |

Demand node | Sum of all outgoing `x` = sum of all incoming `x` + supply quantity `b` . |

Transshipment node | Sum of all outgoing `x` = sum of all incoming `x` |

Since we did not set constraints that `x`

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:_{ij}

- Supply quantities
`b`

are all integers_{i} - Upper bounds
`u`

are all integers._{ij}

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

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

*totally unimodular*For a standard form of linear programs `min {c`

, if A is total unimodular and b are all integers, ^{T} x | A x = b, x ≥ 0}`b ∈ Z`

, then any optimal basic feasible solution ^{m}`x`

obtained by the simplex method must satisfy ^{*}`x`

.^{*} ∈ Z^{n}

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

- All its elemets are either 1, 0 or -1,
- Each column of the matrix contains
two nonzero elements, AND*at most* - 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 `u`

, i.e. there is no constraints on _{ij} = ∞`x`

._{ij}

However, if there is constraints on `x`

, i.e. _{ij}`u`

, 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._{ij} < ∞

## 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 `s`

. The demand of market j is _{i}, i = 1...n`d`

. Between factory i and j, there is a route, the unit cost for shipping one unit from factory i to market j is _{j}, j = 1...m`c`

. Then the problem is “how to ship the product to fulfill all demands while minimizing the total costs?”_{ij}

Obviously this is a special case of MCNF by considering:

- Factories as supply nodes, whose supply quantity is
`s`

_{i} - Markets as demand nodes, whose demand quantity is
`-dj`

- No transshipment nodes
- Arc weights are the unit transportation cost
`c`

_{ij} - No limitations or constraints for arc, i.e.
`u`

_{ij}= ∞ - Also
`Σ`

^{n}_{i=1}s_{i}= Σ^{m}_{j=1}d_{j} - Let
`x`

be the shipping quantity on arc_{ij}`(i, j)`

Possible variants of the problem include:

If `Σ` | We can create a virtual market whose demand quantity is:`d` Arcs to the virtual market have zero costs `c` |

If factory also has cost `c` | Unit transportation cost `c` should be updated to `c` |

If factory also has cost `c` | Unit transportation cost `c` should be updated to `c` |

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

`min Σ`_{i∈I} Σ_{j∈J} c_{ij} x_{ij}
s.t. Σ^{m}_{j=1} x_{ij} = s_{i} ∀i ∈ I
Σ^{n}_{i=1} x_{ij} = d_{j} ∀j ∈ J
x_{ij} ∈ 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 `c`

. Obviously, this problem is a special case of the transportation problem. Jobs are factories and workers are markets._{ij}

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} c_{ij} x_{ij}
s.t. Σ^{n}_{j=1} x_{ij} = 1 ∀i ∈ I
Σ^{n}_{i=1} x_{ij} = 1 ∀j ∈ J
x_{ij} ∈ {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

`b`_{i}

can be zero.```
MCNF
↓ if u
```_{ij} = ∞
Transshipment
↓ if b_{i} ≠ 0
Transportation
↓ if b_{i} = 1 or -1
Assignment

### Shortest Path Problems

For a given network, each arc has a weight `d`

as a distance, then “what is the shortest path to go from a given node _{ij} ≥ 0`s`

to a given node `t`

? A shortest path problem can be formulated as an MCNF problem:

- supply node is
`s`

with supply quantity 1 - demand node is
`t`

with demand quantity -1 - all other nodes are transshipment nodes

Let T be the set of transshipment nodes:

`min Σ`_{i∈I} Σ_{j∈J} d_{ij} x_{ij}
s.t. Σ_{(s,j)∈E} x_{sj} = 1
Σ_{(i,t)∈E} x_{it} = 1
Σ_{(i,k)∈E} x_{ik} - Σ_{(k,j)∈E} x_{kj} = 0 ∀k ∈ T
x_{ij} ∈ {0, 1} ∀(i,j) ∈ E

Shortest path problems is a special case of transshipment problems:

```
Transshipment
↓ if b
```_{s} = 1, b_{t} = -1, b_{i} = 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**.

- The original arcs’ costs are 0, with some limited capacities.
- 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 `x`

be the flow size of the new imaginary arc _{ts}`(t, s)`

, and its cost is `c`

:_{ts} = -1

`min -x`_{ts}
s.t. Σ_{(i,k)∈E} x_{ik} - Σ_{(k,j)∈E} x_{kj} = 0 ∀k ∈ T
x_{ij} ≤ u_{ij} ∀(i,j) ∈ E
x_{ij} ∈ Z+ ∀(i,j) ∈ E

Max flow problems is a special case of MCNF problems:

```
MCNF
↓ if c
```_{ts} = -1, c_{ij} = 0 ∀(i,j) ∈ E
Max Flow

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!

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Tweet