# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 3 Problem Description and Formulation
### Formulation  
A mixed-integer linear problem (MILP) flow-based formulation is proposed and presented in this section to model the CLTPI. This MILP formulation uses binary variables and continuous variables. Before formulating the problem, the following parameters are defined:  
\begin{tabular}{l l} \(n\) & the total number of vertices in graph \(G\), with \(n=|V|\); \\ \(p\) & the number of available locations for plants; \\ \(cl\) & the number of customers to serve, with \(cl=n-p\); \\ \(d_{j}\) & the required demand of the customer \(j\in V_{c}\); \\ \(c_{ij}\) & the cost of establishing a connection using the arc \((i,j)\in A\); \\ \(f_{p}\) & the opening cost for the plant (facility) \(p\in V_{p}\); \\ \(b_{p}\) & the limited capacity of the plant (facility) \(p\in V_{p}\); \\ \(Q\) & the capacity of the connection links. \\ \end{tabular}  
The required variables to formulate the problem are also defined:  
\begin{tabular}{l l l} \(y_{p}\) & = & \(\left\{\begin{array}{ll}1,&\text{if plant $p$ is open,}\\ 0,&\text{otherwise.}\end{array}\right.\) \\ \(x_{ijp}\) & = & \(\left\{\begin{array}{ll}1,&\text{if arc $(i,j)$ is used in the network and is connected to plant $p\in V_{p}$}\\ 0,&\text{otherwise.}\end{array}\right.\) \\ \(t_{ijp}\) & = & the flow passing through arc \((i,j)\) with origin in plant \(p\in V_{p}\) \\ \end{tabular}  
Using the previously defined parameters and variables, the following optimization formulation arises:\[\text{Min}\qquad\sum_{p\in V_{p}}f_{p}y_{p}+\sum_{p\in V_{p}}\sum_{l\in V }\sum_{j\in V_{c}}c_{ij}x_{ijp} \tag{1}\]  
subject to  
\[\sum_{p\in V_{p}}\sum_{\begin{subarray}{c}i\in V\\ i\
eq j\end{subarray}}x_{ijp}=1 \forall j\in V_{c} \tag{2}\] \[\sum_{p\in V_{p}}\sum_{\begin{subarray}{c}i\in V_{c}\\ i\
eq j\end{subarray}}d_{i}x_{ijp}\leq Q-d_{j} \forall j\in V_{c},\] (3) \[\sum_{i\in V}\sum_{\begin{subarray}{c}j\in J_{c}\\ j\
eq i\end{subarray}}d_{j}x_{ijp}\leq b_{p}y_{p} \forall p\in P\] (4) \[\sum_{p\in V_{p}}\sum_{\begin{subarray}{c}i\in V\\ i\
eq j\end{subarray}}t_{ijp}-\sum_{p\in V_{p}}\sum_{\begin{subarray}{c}i\in V _{c}\\ i\
eq j\end{subarray}}t_{ijp}=d_{j} \forall j\in V_{c}\] (5) \[0\leq t_{ijp}\leq Q \forall i\in V,\ j\in V_{c},\ p\in P\] (6) \[x_{ijp}\in\{0,1\} \forall i\in V,j\in V_{c},\ p\in P\] (7) \[y_{p}\in\{0,1\} \forall p\in P \tag{8}\]  
The objective function (1) of the previously presented model minimizes the network's total construction cost. The first term represents the cost of opening the required facilities, while the second represents the cost of establishing the necessary connections for all the vertices in the network. On the other hand, the constraints (2) guarantee that every client vertex is connected to the network, while the constraints (3) limit the number of outgoing arcs from a client vertex, considering the capacity of the links. The plant's capacity is controlled with the constraints (4). To control the links' capacity and the connectivity of the solution, the flow constraints (5) and (6) are used.  
This type of MILP model can be solved by using an exact method (EM) to obtain solutions for the CLTPI. For this research, the EM combines a dual-simplex algorithm with branch-and-bound techniques to solve CLTPI instances.