Network Transformations

Removing Nonzero Lower Bounds

We wish to remove all arcs $(i,j)$ with a non-zero lower bound $l_{ij}$. If we replace $x_{ij}$ by $x_{ij}^{\prime }+l_{ij}$, then the flow bound constraint becomes $0\le x_{ij}^{\prime }\le (u_{ij}-l_{ij})$. The mass balance constraint of node $i$ becomes

$$b(i)=\sum _{(i,k)\in A,k\ne j}{x}_{ik}+x_{ij}^{\prime }+l_{ij}-\sum _{(k,i)\in A}{x}_{ki}$$

and the mass balance constraint of node $j$ is

$$b(j)=\sum _{(j,k)\in A}{x}_{ik}-\sum _{(k,j)\in A,k\ne i}{x}_{ki}-x_{ij}^{\prime }-l_{ij}.$$

Hence, making this replacement requires decreasing $b(i)$ by $l_{ij}$ units and increasing $b(j)$ by $l_{ij}$ units. This effects the objective function by a constant, i.e., the minimum is not changed.

We can do this process by sending $l_{ij}$ units of flow along arc $(i,j)$ and then measure the incremental flow $x_{ij}^{\prime }$ along the arc $(j,i)$. We can then find $x_{ij}$ by adding $l_{ij}$ to $x_{ij}^{\prime }$.

Arc Reversal

Arc reversal can be used to remove arcs with negative costs. We replace the flow $x_{ij}$ with $u_{ij}-x_{ji}$ which replaces the arc $(i,j)$ with an arc $(j,i)$ whose associated cost is $-c_{ij}$. We first send $u_{ij}$ units of flow along the arc to saturate the arc, we then pull back $x_{ji}$ units of flow from $j$ to $i$. Hence we need to flip the arc direction so we can pull back flow. Consider the change to the objective function:

$$c_{ij}{x}_{ij}⟶c_{ij}{u}_{ij}-c_{ij}{x}_{ji}.$$

Thus, changing the cost $c_{ji}=-c_{ij}$ gives the result. Since $c_{ij}<0$, we now get a positive cost arc.

Removing Arc Capacities

We want to remove finite arc capacities resulting in uncapacitated arcs. Assume arc $(i,j)$ has finite capacity $u_{ij}$. We add a new node $k$ so that the capacity constraint along arc $(i,j)$ becomes the mass balance constraint of the new node, i.e.,

$$b(k)=\sum _{(\ell ,k)\in A}{x}_{\ell k}-\sum _{(k,\ell )\in A}{x}_{k\ell }=-u_{ij}.$$

We introduce a slack variable $s_{ij}\ge 0$ so that the capacity constraint $x_{ij}\le u_{ij}$ becomes $x_{ij}+s_{ij}=u_{ij}$. Note now that the flow variable $x_{ij}$ appears in three mass balance constraints: nodes $k$, $i$ and $j$. But $s_{ij}$ only appears in the mass balance constraint for node $k$. We add $u_{ij}$ from the mass balance constraint for node $j$ to get

$$\begin{array}{rl}b(j)+u_{ij}& =\sum _{(j,\ell )\in A}{x}_{j\ell }-\sum _{(\ell ,j)\in A}{x}_{\ell j}+x_{ij}+s_{ij}\\ & =\sum _{(j,\ell )\in A}{x}_{j\ell }-\sum _{(\ell ,j)\in A,\ell \ne i}{x}_{\ell j}+s_{ij}.\end{array}$$

Thus, as a result we now have an arc $(j,k)$ with flow $s_{ij}$. The resulting network is given below:

If $x_{ij}$ is the flow along $(i,j)$ in the original network, then in the transformed network the corresponding flow is $x_{ik}^{\prime }=x_{ij}$ and $x_{jk}^{\prime }=u_{ij}-x_{ij}$. Since $x_{ik}^{\prime }+x_{jk}^{\prime }=u_{ij}$, and both flows are non-negative, we get that $x_{ij}=x_{ik}^{\prime }\le u_{ij}$, i.e., the original capacity constraint still holds in the transformed network. Hence, we can solve this uncapacitated problem and we still get the correct flow $x_{ij}$.

Node Splitting

With node splitting we replace a node $i$ into two new nodes $i^{\prime }$ and $i^{\prime \prime }$ corresponding to the node’s output and input, respectively. We then add a new arc $(i^{\prime \prime },i^{\prime })$ with zero cost and infinite capacity. We replace all inarcs $(j,i)$ with arcs $(j,i^{\prime \prime })$ and all outarcs $(i,j)$ with arcs $(i^{\prime },j)$.

We set the supply/demand for $i^{\prime }$ and $i^{\prime \prime }$ as follows:

1. If $b(i)>0$, then $b(i^{\prime \prime })=b(i)$ and $b(i^{\prime })=0$
2. If $b(i)<0$, then $b(i^{\prime \prime })=0$ and $b(i^{\prime })=b(i)$
3. If $b(i)=0$, then $b(i^{\prime \prime })=b(i^{\prime })=0$