Network Flows

Introduction

Network flow problems are a class of optimization problems that can be used to model a wide range of problems. Network flow problems can be models as linear programs and result in integer solutions.

We can represent a network flow problem as a directed graph \(G = (V, E)\) where \(V\) is the set of nodes and \(E\) is the set of edges. Each edge \((i, j) \in E\) has a capacity \(u_{ij}\) and a cost \(c_{ij}\). The goal is to find the flow \(x_{ij}\) on each edge that minimizes the total cost while satisfying the capacity constraints and flow conservation constraints.

Problem Formulation

The network flow problem (i.e. minimum cost network flow) can be formulated as a linear program as follows:

\[\begin{align*} & \text{Minimize} & & \sum_{(i,j) \in A} c_{ij} x_{ij} \\ & \text{s.t.} & & \sum_{(i,k) \in A} x_{ik} - \sum_{(k,j) \in A} x_{kj} = b_k & \forall k \\ & \text{ } & & 0 \leq x_{ij} \leq u_{ij} & \forall (i,j) \in A \end{align*}\]

where \(A\) is the set of arcs in the network, \(b_k\) is the supply or demand at node \(k\), and \(x_{ij}\) is the flow on arc \((i,j)\). The flow conservation constraints ensure that the flow entering a node minus the flow leaving the node equals the net demand \(b_k\). The capacity constraints ensure that the flow on each arc does not exceed its capacity. The objective function minimizes the total cost of the flow. Capacity u_{ij} and cost c_{ij} are given for each arc. If \(b_k\) is positive, it represents a demand at node \(k\), and if it is negative, it represents a supply at node \(k\). If \(b_k = 0\), it represents a transshipment node.

The conservation of flow contratints can be refresented as two constraints for each node \(k\):

\[\begin{align} \sum_{i \in N_d} x_{ik} &= D_k & \forall k \label{eq:1}\\ \sum_{j \in N_s} x_{kj} &= S_k & \forall k \label{eq:2}\\ \end{align}\]

the difference of the two equations is the same as the original equation where \(b_k = D_k - S_k\).

See examples in the slides.

Transportation Problem

The transportation problem is a special case of the network flow problem where all nodes are either supply nodes or demand nodes. The supply nodes have a supply \(S_i\) and the demand nodes have a demand \(D_j\). The goal is to minimize the total cost of transporting goods from supply nodes to demand nodes while satisfying the supply and demand constraints.

The transportation problem can be formulated as a linear program as follows:

\[\begin{align*} & \text{Minimize} & & \sum_{i \in N} \sum_{j \in M} c_{ij} x_{ij} \\ & \text{s.t.} & & \sum_{j \in M} x_{ij} = S_i & \forall i \in N \\ & \text{ } & & \sum_{i \in N} x_{ij} = D_j & \forall j \in M \\ & \text{ } & & x_{ij} \geq 0 & \forall i \in N, j \in M \end{align*}\]

where \(N\) is the set of supply nodes, \(M\) is the set of demand nodes, \(c_{ij}\) is the cost of transporting goods from supply node \(i\) to demand node \(j\), and \(x_{ij}\) is the amount of goods transported from supply node \(i\) to demand node \(j\). The objective function minimizes the total cost of transporting goods. The supply constraints ensure that the total amount of goods supplied from each supply node equals the supply at that node. The demand constraints ensure that the total amount of goods demanded at each demand node equals the demand at that node.

Assignment Problem

The assignment problem is a special case of the transportation problem where the supply and demand are equal to 1 for each node. The goal is to assign each supply node to exactly one demand node while minimizing the total cost.

The assignment problem can be formulated as a linear program as follows:

\[\begin{align*} & \text{Minimize} & & \sum_{i \in N} \sum_{j \in M} c_{ij} x_{ij} \\ & \text{s.t.} & & \sum_{j \in M} x_{ij} = 1 & \forall i \in N \\ & \text{ } & & \sum_{i \in N} x_{ij} = 1 & \forall j \in M \\ & \text{ } & & x_{ij} \geq 0 & \forall i \in N, j \in M \end{align*}\]

See examples in the slides.

References

1: Optimization in OR textbook by R. Rardin