Minimum Cost Network Flow

Table of Contents

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_i > 0`	supply node, say factory
`b_i < 0`	demand node, say marketplace
`b_i = 0`	transshipment node

Total supplies equal total demands Σ_i∈V b_i = 0. For an arc (i, j) ∈ E, the value u_ij is the upper bound of the flow size (capacity), and the weight c_ij 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 x_ij that we care about, for each of them there are constraints: 0 ≤ x_ij ≤ u_ij. The object function would be to minimize the total cost: 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_ij` = its supply quantity `b_i`.
Demand node	Sum of all outgoing `x_ij` = sum of all incoming `x_ji` + supply quantity `b_i`.
Transshipment node	Sum of all outgoing `x_ij` = sum of all incoming `x_ji`

Since we did not set constraints that x_ij 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:

Supply quantities b_i are all integers
Upper bounds u_ij 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 {c^T x | A x = b, x ≥ 0}, if A is total unimodular and b are all integers, b ∈ Z^m, then any optimal basic feasible solution x^* obtained by the simplex method must satisfy x^* ∈ Zⁿ.

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 at most two nonzero elements, AND
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_ij = ∞, i.e. there is no constraints on x_ij.

However, if there is constraints on x_ij, i.e. u_ij < ∞, 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 s_i, i = 1...n. The demand of market j is d_j, 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 c_ij. 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:

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 Σⁿ_i=1 s_i = Σ^m_j=1 d_j
Let x_ij be the shipping quantity on arc (i, j)

Possible variants of the problem include:

If `Σⁿ_i=1 s_i > Σ^m_j=1 d_j`	We can create a virtual market whose demand quantity is: `d₀ = Σⁿ_i=1 s_i - Σ^m_j=1 d_j` Arcs to the virtual market have zero costs `c_i0 = 0`
If factory also has cost `c^P_i`	Unit transportation cost `c_ij` should be updated to `c_ij + c^P_i`
If factory also has cost `c^R_i`	Unit transportation cost `c_ij` should be updated to `c_ij + c^R_i`

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
     Σⁿ_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_ij. 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 c_ij x_ij
s.t. Σⁿ_j=1 x_ij = 1 ∀i ∈ I
     Σⁿ_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_ij ≥ 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:

supply node is s with supply quantity 1
demand node is twith 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_ts be the flow size of the new imaginary arc (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

My Certificate

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

My 130th certificate from Coursera

Related Quick Recap

Sensitivity Analysis and Dual Simplex Method

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