Unit 3
Let \(G = (\mathcal{N},\mathcal{A})\) be a digraph. To simplify notation, we assume that \(\mathcal{N}= \{v_1,\ldots,v_n\}\) and \(\mathcal{A}= \{e_1,\ldots,e_m\}\) for some integers \(m \geq 0\) and \(n > 0\). Let \(\mathbf{b} \in \mathbb{R}^n\) and \(\mathbf{c} \in \mathbb{R}^m\). The triple \(G, \mathbf{b}, \mathbf{c}\) specifies an uncapacitated network.
In what follows, we call an uncapacitated network simply a network. A network can be interpreted as follows: Imagine that amounts of material move along the arcs in the direction of the arcs. The number \(b_i\) denotes the amount of supply of the material node \(v_i\) has. Node \(v_i\) is called a source if \(b_i > 0\), a sink if \(b_i < 0\), and an intermediate node if \(b_i = 0\). The numbers \(c_j\) denote the cost per unit of material moving along the arc \(e_j\).
A vector \(\mathbf{x} \in \mathbb{R}^m\) is called a flow if it satisfies the flow conservation constraints: \[\sum_{j : e_j \in \delta^{+}(v_i)} x_j - \sum_{j : e_j \in \delta^{-}(v_i)} x_j = b_i,~ \forall~i \in \{1,\ldots,n\}.\] In casual terms, the flow conservation constraints state that the net flow out of node \(v_i\) must equal the amount of supply at node \(v_i\).
A flow \(\mathbf{x}\) satisfying \(\mathbf{x} \geq 0\) is called a feasible flow. The cost of a flow \(\mathbf{x}\) is the quantity \(\mathbf{c}^\mathsf{T}\mathbf{x}\).
We assume that \(\displaystyle\sum_{i = 1}^n b_i = 0\) because otherwise, no flow can exist. We also assume that \(G\) is connected because otherwise, the network is composed of smaller networks.
We are going to study the problem of finding a feasible flow having minimum cost known as the Minimum-Cost Flow Problem. This problem can be formulated as a linear programming problem: \[\begin{array}{rl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ \text{s.t.} & {\mathbf{A}}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{array}\] where \({\mathbf{A}}\) is the node-arc incidence matrix defined as follows: \[a_{ij} = \left\{\begin{array}{rl} 1 & \mbox{if } v_i \mbox{ is the tail of } e_j, \\ -1 & \mbox{if } v_i \mbox{ is the head of } e_j, \\ 0 & \mbox{otherwise}. \end{array}\right.\]
Note that \({\mathbf{A}}\) is an \(n \times m\) matrix (this is the convention commonly used in network flow theory which, unfortunately, differs from the convention we have for specifying the coefficient matrix in that \(m\) and \(n\) are interchanged.) In addition, \({\mathbf{A}}\) has exactly two nonzero entries in each column: one \(1\) and one \(-1\) since every arc has exactly one tail and one head. As a result, the rows of \({\mathbf{A}}\) are not linearly independent because the sum of the rows of \({\mathbf{A}}\) is a row vector of zeros. But one can show that any \(n-1\) rows of \(A\) are linearly independent under our assumption that \(G\) is connected.
We consider the truncated node-arc incidence matrix \(\tilde{{\mathbf{A}}}\) consisting of the first \(n-1\) rows of \({\mathbf{A}}\). Let \(\tilde{\mathbf{b}} = \begin{bmatrix} b_1 & \cdots & b_{n-1}\end{bmatrix}^\mathsf{T}\). Then the above linear programming problem is equivalent to: \[\begin{array}{rl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ \text{s.t.} & \tilde{{\mathbf{A}}}\mathbf{x} = \tilde{\mathbf{b}} \\ & \mathbf{x} \geq \mathbf{0}. \end{array}\]
Consider the digraph depicted in Figure 3.1. The numbers next to the nodes denote the supply values.
The node-arc incidence matrix is \({\mathbf{A}} = \begin{bmatrix} 1 & -1 & 0 & 0 & -1 \\ -1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & -1 & 1 & 0 \end{bmatrix}.\)
The truncated node-arc incidence matrix is \(\tilde{{\mathbf{A}}} = \begin{bmatrix} 1 & -1 & 0 & 0 & -1 \\ -1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 \end{bmatrix}.\)
Let \(T\) be a tree in \(G\) having \(n-1\) arcs. The tree solution determined by \(T\) is a flow \(\mathbf{x} \in \mathbb{R}^m\) such that \(x_j = 0\) for each \(j\) where \(e_j\) is not an arc in \(T\). A tree solution that is also a feasible flow is called a feasible tree solution.
\(\mathbf{x}^* = \begin{bmatrix} 3 & 0 & 3 & 1 & 0\end{bmatrix}^\mathsf{T}\) is a feasible tree solution determined by the tree with arc-set \(\{e_1, e_3, e_4\}\).
The tree solution determined by the tree with arc-set \(\{e_1, e_3, e_5\}\) is \(\mathbf{x}^* = \begin{bmatrix} 2 & 0 & 2 & 0 & -1\end{bmatrix}^\mathsf{T}\) but it is not a feasible tree solution.
Theorem 3.1. A flow \(\mathbf{x}^*\) is a basic solution to \(\tilde{{\mathbf{A}}}\mathbf{x} = \tilde{\mathbf{b}}\) if and only if it is a tree solution.
Corollary 3.2. A flow \(\mathbf{x}^*\) is a basic feasible solution to \(\tilde{{\mathbf{A}}}\mathbf{x} = \tilde{\mathbf{b}},~\mathbf{x} \geq \mathbf{0}\) if and only if it is a feasible tree solution.
If the supply values at all the nodes in a network are integers, then every tree solution has integer entries. This fact can be proved directly from the definition of a tree solution. In this section, we give a proof that uses total unimodularity.
Theorem 3.3. The node-arc incidence matrix of a digraph is totally unimodular.
Recall that the entries of a node-arc incidence matrix of a digraph can only be \(0\), \(1\), or \(-1\). Each column contains exactly one \(1\) and one \(-1\) since each arc has exactly one head and one tail. The result now follows from Proposition 2.1.
Theorem 3.3 together with Theorem 2.2 imply that if a network has integral supply values at all the nodes, then every tree solution has integer entries. This fact leads to immediate applications in some combinatorial optimization problems. We now look at one such problem.
Recall that the assignment problem can be described as follows: There are \(n\) agents and \(n\) tasks. Each agent is to be assigned to exactly one task. The cost of agent \(i\) doing task \(j\) is given by \(c_{ij}\). The problem is to find an assignment of agents to tasks that minimize total cost.
This problem can be formulated as an uncapacitated network flow problem with integral supply values as follows: We have \(n\) nodes, \(p_1,\ldots,p_n\), representing the \(n\) agents and \(n\) nodes, \(t_1,\ldots,t_n\), representing the \(n\) tasks. For each \(p_i\) representing a agent and each \(t_j\) representing a task, there is an arc from \(p_i\) to \(t_j\) with arc cost \(c_{ij}\). At each node representing a agent, the amount of supply is \(1\), indicating that one agent is available to be assigned. At each node representing a task, the amount of supply is \(-1\), indicating that one agent is needed for the task. So the problem is to find a minimum-cost integer feasible flow in the network. By the corollary above, we simply need to find a minimum-cost feasible tree solution in the network.
Now, the assignment problem can be formulated as the following linear programming problem:
\[\begin{array}{rll} \min & \displaystyle\sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij} \\ \text{s.t.} & \displaystyle\sum_{j = 1}^n x_{ij} = 1 & i = 1,\ldots, n \\ & -\displaystyle\sum_{i = 1}^n x_{ij} = -1 & j = 1,\ldots, n \\ & x_{ij} \geq 0 & \text{for all } i, j \in \{1,\ldots,n\}, \end{array}\] a formulation that we have already seen in Unit 2.
We note in closing that the rewritten form \[\begin{array}{rll} \min & \displaystyle\sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij} \\ \text{s.t.} & \displaystyle\sum_{j = 1}^n x_{ij} = 1 & i = 1,\ldots, n \\ & \displaystyle\sum_{i = 1}^n x_{ij} = 1 & j = 1,\ldots, n \\ & x_{ij} \geq 0 & \text{for all } i, j \in \{1,\ldots,n\} \end{array}\] often appears in the study of bipartite perfect matching which we will study later in this course.
We have now seen that tree solutions correspond to basic feasible solutions in a specific way. The simplex method can now be specialized to network flows to give the following algorithm known as Network Simplex Method.
Input: A network \(G,\mathbf{b},\mathbf{c}\) where \(G=(\mathcal{N},\mathcal{A})\) is a digraph with \(\mathcal{N}=\{v_1,\ldots,v_n\}\) and \(\mathcal{A}=\{e_1,\ldots,e_m\}\) and a feasible tree solution \(\mathbf{x}^*\) determined by the tree having arc set \(T\).
Steps:
Let \(N = \mathcal{A}\backslash T\).
Obtain \(y_1,\ldots,y_n\) such that \(y_n = 0\) and for each \(e_j \in T\), \(y_p - y_q = c_j\) where \(p\) and \(q\) are such that \(v_p\) is the tail of \(e_j\) and \(v_q\) is the head of \(e_j\).
Choose \(k \in \{1,\ldots, m\}\) such that \(e_k \in N\) and \(y_p - y_q > c_k\) where \(p\) and \(q\) are such that \(v_p\) is the tail of \(e_k\) and \(v_q\) is the head of \(e_k\). If no such \(k\) exists, then stop; \(\mathbf{x}^*\) is a minimum-cost feasible flow.
Let \(C\) be the unique cycle in \(T\cup \{e_k\}\).
If \(C\) is a dicycle, then stop; the problem is unbounded.
Let \(R\) be the set of arcs in \(C\) not oriented in the same direction as \(e_k\). Set \(\theta = \min\{x^*_j : e_j \in R\}\) and choose \(r \in \{1,\ldots,m\}\) such that \(e_r \in R\) and \(x^*_r = \theta\).
Update \(\mathbf{x}^*\) as follows: \[x^*_j = \left\{\begin{array}{ll} x^*_j + \theta & \text{ if } e_j \in C\backslash R,\\ x^*_j - \theta & \text{ if } e_j \in R,\\ x^*_j & \text{ otherwise.} \end{array}\right.\]
Replace \(T\) with \((T\cup \{e_k\})\backslash \{e_r)\}\) and go to step 1.
Remarks.
The above algorithm is a specialization of the simplex method to the network setting. In the remarks below, we highlight some of the steps that have been specialized.
In step 2, since \(y_n = 0\) (node \(v_n\) is usually called the root, one is really solving \(\begin{bmatrix} y_1 & \cdots & y_{n-1}\end{bmatrix} \tilde{{\mathbf{A}}}_B = \mathbf{c}_B^\mathsf{T}\) where \(\tilde{{\mathbf{A}}}\) is the truncated node-arc incidence matrix and \(B = \{j : e_j \in T\}\).
In step 3, the chosen arc \(e_k\) is called the entering arc.
In step 5, the total cost of the arcs can be seen to be negative. Since \(C\) is a dicycle, increasing the amount of flow on each arc in \(C\) by the same amount still gives a feasible flow and so cost of the flow can be made arbitrarily negative.
In step 6, the arcs in \(C\) oriented not in the same direction as \(e_k\) are precisely the backward arcs in a walk giving the cycle \(C\) such that \(e_k\) is a forward arc in the walk. The arc \(e_r\) is called the leaving arc.
Consider the network consisting of the digraph depicted in Figure 3.2 with \(\mathbf{b} = \begin{bmatrix} 4 & -1 & -1 & -2\end{bmatrix}^\mathsf{T}\) and \(\mathbf{c} = \begin{bmatrix} 3 & 1 & 2 & 1 & 1 & 2\end{bmatrix}^\mathsf{T}\).
Find a minimum-cost flow starting with the feasible tree solution determined by the tree having arc-set \(T = \{e_1, e_3, e_6\}\).
The tree solution determined by the given tree is \(\mathbf{x}^* = \begin{bmatrix} 4&0&3&0&0&2\end{bmatrix}^\mathsf{T}\).
Iteration 1.
\(N = \{e_2,e_4,e_5\}\).
Solving for \(y_1,\ldots,y_4\), we get \(\begin{bmatrix} y_1 & y_2 & y_3 & y_4\end{bmatrix}^\mathsf{T}= \begin{bmatrix} 7 & 4 & 2 & 0\end{bmatrix}^\mathsf{T}\).
Choose \(k = 2\) since \(y_1-y_3 = 5 > 1 = c_2\)
\(C = \{e_1,e_2,e_3\}\).
\(C\) is not a dicycle.
\(R = \{e_1,e_3\}\). \(\theta = \min\{x^*_1, x^*_3\} = \min\{4,3\} = 3\). Choose \(r = 3\).
New \(\mathbf{x}^* = \begin{bmatrix} 1 & 3 & 0 & 0 & 0 & 2\end{bmatrix}^\mathsf{T}\).
New \(T = \{e_1,e_2,e_6\}\).
Iteration 2.
\(N = \{e_3,e_4,e_5\}\).
Solving for \(y_1,\ldots,y_4\), we get \(\begin{bmatrix} y_1 & y_2 & y_3 & y_4\end{bmatrix}^\mathsf{T}= \begin{bmatrix} 3 & 0 & 2 & 0\end{bmatrix}^\mathsf{T}\).
Choose \(k = 4\) since \(y_3-y_2= 2 > 1 = c_4\)
\(C = \{e_1,e_2,e_4\}\).
\(C\) is not a dicycle.
\(R = \{e_1\}\). \(\theta = \min\{x^*_1\} = 1\). Choose \(r = 1\).
New \(\mathbf{x}^* = \begin{bmatrix} 0 & 4 & 0 & 1 & 0 & 2\end{bmatrix}^\mathsf{T}\).
New \(T = \{e_2,e_4,e_6\}\).
Iteration 3.
\(N = \{e_1,e_3,e_5\}\).
Solving for \(y_1,\ldots,y_4\), we get \(\begin{bmatrix} y_1 & y_2 & y_3 & y_4\end{bmatrix}^\mathsf{T}= \begin{bmatrix} 3 & 1 & 2 & 0\end{bmatrix}^\mathsf{T}\).
Since \[\begin{align*} y_1-y_2 & = 2 < 3 = c_1, \\ y_2-y_3 & = -1 < 2 = c_3, \\ y_2-y_4 & = 1 = c_5, \end{align*}\] \(\mathbf{x}^* = \begin{bmatrix} 0 & 4 & 0 & 1 & 0 & 2\end{bmatrix}^\mathsf{T}\) is a minimum-cost feasible flow.
Let \(G = (\mathcal{N}, \mathcal{A})\) denote the digraph depicted below:
Let \(\mathbf{b} = \begin{bmatrix} 3 & -1 & -1 & 1 & -2 \end{bmatrix}^\mathsf{T}\).
Let \(\mathbf{c} = \begin{bmatrix} 0 & -1 & 2 & 3 & 4 & 5 & 6 & -7 \end{bmatrix}^\mathsf{T}\).
Write down the node-arc incidence matrix of \(G\).
Write out explicity the flow conservation constraint at node \(v_2\).
Recall that the flow conservation constraints are: \[\sum_{j : e_j \in \delta^{+}(v_i)} x_j - \sum_{j : e_j \in \delta^{-}(v_i)} x_j = b_i,~ \forall~i \in \{1,\ldots,n\}.\]
Let \({\mathbf{A}}\) denote the node-arc incidence matrix of \(G\). Write down explicitly the problem \[\begin{array}{rl} \min & \mathbf{y}^\mathsf{T}\mathbf{b} \\ \text{s.t.}& \mathbf{y}^\mathsf{T}{\mathbf{A}} \leq \mathbf{c}^\mathsf{T}\\ \end{array}\]
Obtain a feasible tree solution by inspection and apply the Network Simplex Method starting with this tree solution.
The node-arc incidence matrix is \[\begin{bmatrix} 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 0 & -1 & -1 & 1 \end{bmatrix}.\]
Note that \(\delta^{+}(v_2) = \{e_4, e_6\}\), \(\delta^{-}(v_2) = \{e_1\}\), and \(b_2 = -1\). Hence, the flow conservation constraint at \(v_2\) is \[x_4+x_6 - x_1 = -1.\] This can be written is matrix form as \[\begin{bmatrix} -1 & 0 & 0 & 1 & 0 & 1 & 0 & 0\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8\end{bmatrix} = -1.\] Note that the coefficient matrix is the same as the second row of the node-arc incidence matrix.
The problem is \[\begin{array}{rrcrcrcrcrcc} \max & 3y_1 & - & y_2 & - & y_3 & + & y_4 & - & 2y_5 \\ \text{s.t.}& y_1 & - & y_2 & & & & & & & \leq & 0 \\ & y_1 & & & & & - & y_4 & & & \leq & -1 \\ & -y_1 & & & & & & & + & y_5 & \leq & 2 \\ & & & y_2 & - & y_3 & & & & & \leq & 3 \\ & & & & &-y_3 & + & y_4 & & & \leq & 4 \\ & & & y_2 & & & & & - & y_5 & \leq & 5 \\ & & & & & y_3 & & & - & y_5 & \leq & 6 \\ & & & & & & & -y_4 & + & y_5 & \leq & -7 \end{array}\]
The tree with arc-set \(T = \{e_1, e_4, e_5, e_6\}\) determines the feasible tree solution \(\mathbf{x}^* = \begin{bmatrix} 3 & 0 & 0 & 0 & 1 & 2 & 0 & 0 \end{bmatrix}^\mathsf{T}\). We apply the Network Simplex Method starting with \(\mathbf{x}^*\):
Iteration 1.
\(N = \{e_2,e_3,e_7,e_8\}\).
Solving \[\begin{align*} y_1 - y_2 & = c_1 = 0 \\ y_2 - y_3 & = c_4 = 3 \\ y_4 - y_3 & = c_5 = 4 \\ y_2 - y_5 & = c_6 = 5 \\ y_5 & = 0 \end{align*}\] for \(y_1,\ldots,y_5\), we get \(\begin{bmatrix} y_1 & y_2 & y_3 & y_4 & y_5 \end{bmatrix}^\mathsf{T}= \begin{bmatrix} 5 & 5 & 2 & 6 & 0\end{bmatrix}^\mathsf{T}\).
Choose \(k = 8\) since \(y_5-y_4 = -6 > -7 = c_8\).
\(C = \{e_4,e_5,e_6,e_8\}\).
\(C\) is not a dicycle.
\(R = \{e_4\}\). \(\theta = \min\{x^*_4\} = 0\). Choose \(r = 4\).
New \(\mathbf{x}^* = \begin{bmatrix} 3 & 0 & 0 & 0 & 1 & 2 & 0 & 0\end{bmatrix}^\mathsf{T}\).
New \(T = \{e_1,e_5,e_6,e_8\}\).
Iteration 2.
\(N = \{e_2,e_3,e_4,e_7\}\).
Solving \[\begin{align*} y_1 - y_2 & = c_1 = 0 \\ y_4 - y_3 & = c_5 = 4 \\ y_2 - y_5 & = c_6 = 5 \\ y_5 - y_4 & = c_8 = -7 \\ y_5 & = 0 \end{align*}\] for \(y_1,\ldots,y_5\), we get \(\begin{bmatrix} y_1 & y_2 & y_3 & y_4 & y_5 \end{bmatrix}^\mathsf{T}= \begin{bmatrix} 5 & 5 & 3 & 7 & 0\end{bmatrix}^\mathsf{T}\).
There is no \(k\) such that \(e_k \in N\) \(y_p - y_q > c_k\) where \(p\) and \(q\) are such that \(v_p\) is the tail of \(e_k\) and \(v_q\) is the head of \(e_k\). The algorithm stops and \(\mathbf{x}^*\) is a minimum-cost feasible flow.