# Optimization of Multimodal Discrete Network Design Problems Based on Super Networks
## 4 Solution Algorithm
### Minimum Cost Flow Algorithm  
Let \(\mu_{k}\) be the minimum cost augmentation chain of the \(k\)-th iteration, \(\varepsilon_{k}\) be the adjustable flow on the augmentation chain \(\mu_{k}\), and \(x^{k}\) be the feasible flow of the \(k\)-th iteration. Based on the shortest path method, a network \(L(x)\) is constructed, whose nodes are the nodes of the original network \(G\), specifically, the link \((v_{i},v_{j})\) of the original network \(G\) is changed into two links with opposite directions \((v_{i},v_{j})\) and \(\big{(}v_{j},v_{i})\). Define the weights of links \((v_{i},v_{j})\) and \(\big{(}v_{j},v_{i})\) in \(L(x)\) as \(l_{ij}\) and \(l_{ji}\):  
\[l_{ij}=\left\{ \begin{array}{ll}w_{ij}&\text{if}\;\;x_{ij}<c_{ij}\\ +\infty&\text{if}\;\;x_{ij}=c_{ij}\end{array} \right., \tag{33}\]\[l_{ji}=\left\{ \begin{array}{ll}-w_{ij}&\text{if}&x_{ij}>0\\ +\infty&\text{if}&x_{ij}=0\end{array} \right. \tag{34}\]  
Set the matrix \(\mathbf{D}=\left(d_{ij}\right)_{n\times n^{\prime}}\)\(d_{ij}\) represents the shortest length from \(v_{i}\) to \(v_{j}\) in the original network \(G\); \(\mathbf{S}=\left(s_{ij}\right)_{n\times n^{\prime}}\)\(s_{ij}\) represents the end number of the first link of the shortest path from \(v_{i}\) to \(v_{j}\). For example, if \(s_{ij}^{(n)}=t\), the first link of the shortest path from \(v_{i}\) to \(v_{j}\) is \(\left(v_{i},v_{t}\right)\). Above all, the algorithm for solving the minimum cost feasible flow with the target flow \(q_{rs}\) is as follows:  
_Step 1_: Set \(k=0\)  
Start with a minimum cost initial feasible flow \(x^{(0)}\), \(\left(x^{(0)}\leq q_{rs}\right)\) (generally, \(x^{(0)}=0\)). _Step 2_: Generate \(L\left(x^{(k)}\right)\), find the minimum cost path from \(v_{r}\) to \(v_{s}\) in \(L\left(x^{(k)}\right)\), and use the Floyd algorithm to solve the shortest path. _Step 2.1_: Set \(m=0\)  
\[\mathbf{D}^{(0)}=\left(d_{ij}^{(0)}\right)_{n\times n},d_{ij}^{(0)}=\left\{ \begin{array}{ll}w_{ij}&\left(v_{i},v_{j}\right)\in A\\ \infty&\left(v_{i},v_{j}\right)\
otin A\\ 0&v_{i}=v_{j}\end{array} \right. \tag{35}\]  
\[\mathbf{S}^{(0)}=\left(s_{ij}^{(0)}\right)_{n\times n}\mathbf{s}_{ij}^{(0)}=j(i,j=1,2,\cdots,n). \tag{36}\]  
_Step 2.2_: \(m=m+1\)  
Calculate:  
\[\mathbf{D}^{(m)}=\left(d_{ij}^{(m)}\right)_{n\times n}\mathbf{S}^{(m)}=\left(s_{ij}^{( m)}\right)_{n\times n} \tag{37}\]  
where:  
\[d_{ij}^{(m)}=min\Big{\{}d_{ij}^{(m-1)},d_{im}^{(m-1)}+d_{mj}^{(m-1)}\Big{\}}, \tag{38}\]  
\[s_{ij}^{(m)}=\left\{ \begin{array}{ll}s_{ij}^{(m-1)}&d_{ij}^{(m-1)}\leq d_{ im}^{(m-1)}+d_{mj}^{(m-1)}\\ s_{im}^{(m-1)}&d_{ij}^{(m-1)}\geq d_{im}^{(m-1)}+d_{mj}^{(m-1)}\end{array}  \right.. \tag{39}\]  
If \(m\
eq n\) go to step 2.2, else go to step 2.3. _Step 2.3_: when \(m=n\), the algorithm ends. \(\mathbf{D}^{(n)}=\left(d_{ij}^{(n)}\right)_{n\times n}\), \(d_{ij}^{(n)}\) is the shortest path length from \(v_{i}\) to \(v_{j}\);  
\(\mathbf{S}^{(n)}=\left(s_{ij}^{(n)}\right)_{n\times n^{\prime}}\), \(s_{ij}^{(n)}\) is the end node of the first link in the shortest path from \(v_{i}\) to \(v_{j}\). _Step 3_: If \(L\left(x^{(k)}\right)\) does not have the shortest path from \(v_{r}\) to \(v_{s}\), then \(x^{(k)}\) is regarded as the maximum flow, there is no minimum cost flow with the target flow of \(q_{rs}\), end the algorithm; otherwise, go to the next step. _Step 4_: Find the augmented chain \(\mu_{k}\) corresponding to the shortest path from \(v_{r}\) to \(v_{s}\) in \(L\left(x^{(k)}\right)\) in the original network \(G\), and calculate \(\varepsilon_{k}=\min\Big{\{}\min\Big{(}c_{ij}-x_{ij}^{k}\Big{)},\ \min\ x_{ij}^{k}\Big{\}}\).