# Hub-and-Spoke Network Design Considering Congestion and Flow-Based Cost Function
## Appendix A Linearization of Nonlinear Constraints  
In the proposed models, there are nonlinear constraints. The nonlinearity of the model is inevitable but adds to the complexity of the solution procedure and makes the solution less reliable. To overcome such issues, we apply linearization techniques to linearize the nonlinear constraints. Nonlinear constraints of the utility function  
The flow transported from node \"i\" to node \"j\" is  
\[w_{ij}=\sum_{m,n}P_{mm}\frac{U_{mmij}\cdot s_{i}s_{j}}{\sum_{o,d}U_{mmod}s_{o} s_{d}},\hskip 28.452756 pti,j\
eq i \tag{1}\]  
which is a nonlinear expression. To linearize, we implement a set of substitutions and additional constraints to give us an equivalent formulation in a linear form. We define the probability of choosing a path i-j for demand from m to n, such as  
\[prob(m,n,i,j)=\frac{U_{mmij}\cdot s_{i}s_{j}}{\sum_{o,d}U_{mmod}s_{o}s_{d}} \tag{2}\]  
Thus, we have the demand of m to n going through i and j:  
\[P_{mm}prob(m,n,i,j)=dem(m,n,i,j) \tag{3}\]  
where \(dem(m,n,i,j)\) is the final, calculated demand from \"m\" to \"n\" which uses \"i\" as the origin node and \"j\" as the destination on the network. Based on this, we have  
\[w_{ij}=\sum_{m,n}dem(m,n,i,j),\hskip 28.452756 pti,j\
eq i \tag{4}\]  
This is a nonlinear constraint, which adds to the complexity of the model and is not easy to solve. To address this issue, we implement mathematical techniques to linearize the first set of constraints, as also used by [PERSON] and [PERSON] (2017) [35]:  
\[prob(m,n,i,j)\leq s_{i}\hskip 28.452756 pt\forall i,j,m,n \tag{5}\]  
\[prob(m,n,i,j)\leq s_{j}\hskip 28.452756 pt\forall i,j,m,n \tag{6}\]Constraints (A5) and (A6) ensure that \(prob(m,n,i,j)\) cannot take any value if there is not any spoke established on node i or node j.  
\[\sum_{i,j}prob(m,n,i,j)+prob(m,n,a,b)=1\hskip 28.452756 pt\forall m,n\] (A7)  
The constraint (A7) which can be somehow considered as the \"flow constraint\" states that the initial demand from starting point \"m\" to final destination \"n\" would be either transported via some O-D pair of (i, j) or would be lost (going to dummy points \"a\" and \"b\"). \[prob(m,n,i,j)\leq\frac{u_{mmij}}{u_{mmkl}}.prob(m,n,k,l)+1-s_{k}\cdot s_{l} \hskip 28.452756 pt\forall i,j,m,n,k,l\] (A8)  
The constraint (A8) essentially expresses that the transported flow via O-D (i, j) compared to the transported flow via O-D (k, l) is proportional to their utilities. This is proven by [PERSON] and [PERSON] (2017) [35]. The nonlinear term in (A8) is linearized, as shown below:  
\[s_{i}\cdot s_{j}=s_{ij}\hskip 28.452756 pt\forall i,j\] (A9)  
\[s_{i}+s_{j}-1\leq s_{ij}\hskip 28.452756 pt\forall i,j\] (A10)  
\[prob(m,n,i,j)=\frac{U_{mmij}\cdot s_{i}s_{j}}{\sum_{o,d}U_{mmod}s_{o}s_{d}} \tag{2}\]0 (A11)  
Using this equivalent set of constraints, the formulation comes into a mixed-integer linear programming (MILP) model. The drawback is the large number of constraints produced by (A9)-(A11). Linearization of the multiplication of two variables  
In the objective function, both \(w_{ij}\) and \(x_{ijkl}\) are decision variables; thus, the term \(w_{ij}x_{ijkl}\) is the multiplication of two variables and is not linear. As initially defined in the problem definition, we have \(x_{ijkl}\in(0,1)\), which is a continuous variable, but in the absence of the congestion constraint in the optimal solution, we would have \(x_{ijkl}\in\{0,1\}\) since if there is an optimal path from an origin point i to destination point j, traversing hub link k-l, the whole flow would choose that path. Therefore, we can treat \(x_{ijkl}\) as a binary variable.