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.

The node i is a
bi > 0supply node, say factory
bi < 0demand node, say marketplace
bi = 0transshipment node

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.

Supply nodeSum of all outgoing xij
= its supply quantity bi.
Demand nodeSum of all outgoing xij
= sum of all incoming xji + supply quantity bi.
Transshipment nodeSum of all outgoing xij
= sum of all incoming xji

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:

If ฮฃni=1 si > ฮฃmj=1 djWe can create a virtual market whose demand quantity is:
d0 = ฮฃni=1 si - ฮฃmj=1 dj
Arcs to the virtual market have zero costs ci0 = 0
If factory also has cost cPiUnit transportation cost cij should be updated to cij + cPi
If factory also has cost cRiUnit transportation cost cij should be updated to cij + cRi

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.

 โ†“ if uij = โˆž
 โ†“ if bi โ‰  0
 โ†“ if bi = 1 or -1

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 twith 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:

 โ†“ 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:

 โ†“ 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

Related Quick Recap

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at

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!