# Hub-and-Spoke Network Design Considering Congestion and Flow-Based Cost Function
## Appendix B Tightening the Formulation  
We use several linearization techniques to convert the MINLP model presented in Section 3 to an MILP model. The proposed model is still a large-scale problem and is not easy to tackle by increasing the number of nodes in the network. In this section, we apply some preprocessing rules and add valid inequalities to achieve a tighter formulation in order to improve the proposed MILP and help the solution procedure. The idea of implementing preprocessing techniques and tightening rules was also used in the literature by [PERSON] et al. (2016) and [PERSON] (2017).  
1. Preprocessing  
The following rules are applied as preprocessing techniques:  
It is not optimal for all \(y_{kl}\) variables to take values. These variables can take value (1) if and only if both end nodes are hub nodes. As a result, there should be some demands that in the optimal solution traverse the hub link k-l. This should economically be optimal; in other words, the cost of transportation from origin node (i) to first hub (k), transportation on the hub link \(y_{kl}\), and the transportation cost from hub (l) to destination (j) outperforms the cost of direct (or any other combination on the path) transportation. This can be shown mathematically as  
\[\
exists a,b:d_{ak}+\alpha\cdot d_{kl}+d_{lb}<\min_{m,n}\{d_{am}+d_{mb},d_{am}+ \alpha\cdot d_{mn}+d_{nb},d_{an}+d_{nb}\}\Rightarrow y_{kl}=0 \tag{116}\]  
An argument can be constructed around the satisfied demand of any (i, j) node pairs (\(w_{ij}\)) as follows:  
The total satisfied demand, by comparing the lost demand cost with the transportation cost is as follows:  
\[B\sum_{i,j}w_{ij}\leq\sum_{i,j}w_{ij}\min_{k,l}\Bigl{\{}d_{ik}+\alpha d_{kl}+d _{lj}\Bigr{\}}+\min_{k,l}(cs_{k}+cs_{l})+\min_{k,l}(h_{k})+\min_{k,l}(y_{kl}) \tag{117}\]  
The above inequality states that up to a certain level of satisfied/transported demand \((\sum_{i,j}w_{ij})\), the model decides to lose all the demand, rather than satisfy it. [It is also intuitive: for few demand nodes/demand volumes, it is not economically feasible to establish a hub/spoke facility or any link between those]. Therefore, this relation would give the model a minimum value of total satisfied demand, which can be added as an integer cut to the problem:  
\[\begin{cases}\begin{array}{c}\sum\limits_{ij}w_{ij}<\widetilde{w}_{ij};\text { {\it lost\ the\ demand\ }}w_{ij}\\ \sum\limits_{ij}w_{ij}\geq\ \widetilde{w}_{ij};\text{{\it transport\ the\ demand\ }}w_{ij}\end{array}\end{cases} \tag{118}\]where \[\widetilde{w}_{ij}=\frac{\sum_{i,j}w_{ij}\cdot\min_{k,l}\left\{d_{ik}+\alpha\cdot d_ {kl}+d_{lj}\right\}+\min_{k,l}(cs_{k}+cs_{l})+\min_{k,l}(h_{k})+\min_{k,l}(y_{ kl})}{B}\] (10)
2. Tightening In addition to the preprocessing techniques, we present some valid inequalities by investigating the features of the developed mathematical model. These inequalities can make the formulation a tighter one, in terms of the gap between the LP relaxation of the model and the integer polyhedral. This argument can be further extended as an elimination bound to exclude some hub nodes. Hence, it is easy to follow that for any node i, we can state \[\sum_{j}(y_{ij}+y_{ji})=0\Longrightarrow h_{i}=0\hskip 28.452756 pt\forall i\] (11) we applied this by adding the following cut to the problem: \[h_{i}\leq\sum_{j}\left(y_{ij}+y_{ji}\right)\hskip 28.452756 pt\forall i\] (12)  
In addition, considering the characteristics of a connected graph leads us to have  
\[\sum_{k,l}y_{kl}\geq\sum_{k}h_{k} \tag{13}\]  
We can also substitute the value of large M, as a large constant, with relevant model parameters to further tighten the formulation using  
\[M=\sum_{i,j}w_{ij} \tag{14}\]