# Hub-and-Spoke Network Design Considering Congestion and Flow-Based Cost Function
## 4 Solution Approach
### Sub-Problem  
Once the master problem is solved, we need to solve the sub-problem, generate valid inequalities (the integer cuts), add those to the master problem, and solve the master problem again, until the stopping criteria happen (either convergence or a certain number of cycles). In the master problem, the location of the hub-and-spoke facilities is determined, as well as the hub links in the hub network graph. Once the location of the spoke facilities is known, we can calculate the demand of each node, using the utility relations explained earlier. Therefore, for the sub-problem, the values of \(w_{ij}\) are fixed and known and are parameters, rather than variables, as in the integrated model.  
The sub problem essentially deals with the transportation problem, which also decides upon the flow of hub links. We define the cost function of hub links as a function of the traversed flow. In simple words, we need to know the flow to put the correct value of (\(\alpha\)) (which is needed to solve the sub problem), while we first need to solve the sub problem to determine the traversed flow. To overcome this interdependency, we develop a heuristic Algorithm 1 that can be described as follows:  
```
Step 1 : Put the initial value of \(\alpha_{kl}=\alpha_{kl}^{2}\) Step 2: Run the sub-problem Step 3: For every pair of (\(k,l\)) if \(\sum\limits_{j\
eq i}w_{ij}x_{ijkl}<b\) then \(\alpha_{kl}\gets\alpha_{kl}^{1}\)
```  
**Algorithm 1** Sub-Problem  
We can then write the sub-problem, assuming fixed values for \(\alpha_{kl}\), as follows:  
\[\min\theta=\sum_{i}\sum_{j\
eq i}\sum_{k}\sum_{l\
eq k}\alpha w_{ij}C_{kl}x_{ ijkl}+\sum_{i}\sum_{j\
eq i}\sum_{k\
eq i,j}w_{ij}C_{ik}a_{ijk}+\sum_{i}\sum_{j \
eq i}\sum_{k\
eq i,j}w_{ij}C_{kj}b_{ijk}+\sum_{i}\sum_{j\
eq i}w_{ij}C_{ji}e _{ij} \tag{43}\]  
Subject to  
\[\sum_{l\
eq i}x_{ijil}+\sum_{l\
eq i,j}a_{ijl}+e_{ij}=zi,\hskip 28.452756 ptj\
eq i \tag{44}\]  
\[\sum_{l\
eq i}x_{ijl}+\sum_{l\
eq i,j}b_{ijl}+e_{ij}=z,i,\hskip 28.452756 ptj\
eq i \tag{45}\]  
\[\sum_{l\
eq k,i}x_{ijkl}+b_{ijk}=\sum_{l\
eq k,j}x_{ijlk}+a_{ijk},\hskip 28.452756 pti,j\
eq i,k\
eq i,j \tag{46}\]  
\[x_{ijkl}\leq y_{kl},\hskip 28.452756 pti,j\
eq i,k,l \tag{47}\]\[\sum\limits_{l\
eq k}x_{kjkl}\leq h_{k},\hskip 28.452756 ptj,k\
eq j \tag{48}\]  
\[\sum\limits_{k\
eq l}x_{ilkl}\leq h_{l},\hskip 28.452756 pti,l\
eq i \tag{49}\]  
\[a_{ijk}\leq 1-h_{i},\hskip 28.452756 pti,j\
eq i,k\
eq i,j \tag{50}\]  
\[b_{ijl}\leq 1-h_{j},\hskip 28.452756 pti,j\
eq i,k\
eq i,j \tag{51}\]  
\[a_{ijk}+\sum\limits_{l\
eq j,k}x_{ijkl}\leq h_{k},\hskip 28.452756 pti,j\
eq i,k \
eq i,j \tag{52}\]  
\[b_{ijk}+\sum\limits_{l\
eq k,i}x_{ijkl}\leq h_{k},\hskip 28.452756 pti,j\
eq i,k \
eq i,j \tag{53}\]  
\[e_{ij}+2x_{ijij}+\sum\limits_{l\
eq j,i}x_{ijil}+\sum\limits_{l\
eq i,j}x_{ij ij}\leq h_{i}+h_{j}\hskip 28.452756 pti,j\
eq i \tag{54}\]  
\[\sum\limits_{i}\sum\limits_{j\
eq i}\sum\limits_{l\
eq k}w_{ij}x_{ijkl}+\sum \limits_{i}\sum\limits_{j\
eq i}\sum\limits_{l\
eq k}w_{ij}x_{ijlk}+\sum \limits_{i\
eq k}\sum\limits_{j\
eq i}w_{ij}a_{ijk}+\sum\limits_{i\
eq k} \sum\limits_{j\
eq i}w_{ij}b_{ijk}\]  
\[\hskip 28.452756 pt+\sum\limits_{i\
eq k}2w_{ik}e_{ik}+\sum\limits_{i\
eq k}2w_ {ki}e_{ki}+\sum\limits_{i}\sum\limits_{j\
eq i}\sum\limits_{l\
eq i}\sum\limits _{k}w_{ij}x_{ijkl}\cdot h_{i}h_{j}\]  
\[+\sum\limits_{i}\sum\limits_{j\
eq i}\sum\limits_{l\
eq k}w_{ij}x_{ijlk}h_{ i}h_{j}=2g_{k}\hskip 28.452756 pt\forall k\in K\]  
\[g^{Max}=\max\limits_{k}(g_{k}),g^{Min}=\min\limits_{k}^{\min}(g_{k}),\hskip 28.452756 pt \forall k\in K \tag{56}\]  
\[g^{Max}\leq\
abla\cdot g^{Min} \tag{57}\]  
\[x_{ijkl},a_{ijk},b_{ijk},e_{ij}\in(0,1)\]  
\[g^{Max},g_{k}\in R^{+}\]