# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 4 CLTPI Solution Algorithms
### Decoder with Improvement Phase
The lists are initialized in lines 3 to 5. The assignation of clients is performed in the loop in lines 7 to 40. In each iteration, \(i\) denotes the vertex to be assigned (initialized in line 6). In line 7, an ordered list is built using open plants and clients already assigned, which are stored in the list ASSIGNED. The loop in lines 10 to 29 assigns the vertex \(i\) to the closest \(s\)-tree or plant with available capacity. If the client \(i\) is assigned to an \(s\)-tree, the vectors \(a\), \(s\), and \(r\) are updated in lines 13 to 16. If \(i\) is directly connected to a plant, the vectors \(a\), \(s\), and \(r\) are updated in lines 19 to 22. If assigned, the client \(i\) is removed from the list VERTICES and included in the list ASSIGNED in lines 25 and 26. If there is no \(s\)-tree or plant with available capacity to accommodate \(i\), then a new plant, \(k\), is open, and the client \(i\) is directly connected to it and included in the list ASSIGNED (lines 30 to 37). The proposed decoder is a two-phase decoder. In the first phase, the key vector is decoded and transformed into a solution of the CLPTI, while in the second phase, the obtained solution is improved. For the CLTPI, the improvement phase re-optimizes \(s\)-trees by computing an MST since \(s\)-trees respect the link capacity constraints. The MST is computed for the set of vertices contained in the \(s\)-tree plus the plant to which the \(s\)-tree is connected using [PERSON]'s algorithm [6]. ```
procedurecost-based assignment Input:\(\mathcal{X}_{p},\mathcal{X}_{c},V,A,V_{p},V_{c},f,Q,d,c,MPR\) Output: Assignment array a \(a(p)\gets 0,s(p)\gets f(p)\), for \(p\in V_{p}\) \(a(i)\gets 0\), \(r(i)\gets 0,s(i)\gets Q\), for \(i\in V_{c}\)  Initialize list VERITICES with vertices \(1,\in V_{c}\) in increasing order of \(\mathcal{X}_{c}\);  Initialize list ASSIGNED with vertices \(1,\ldots,MP\) in increasing order of \(\mathcal{X}_{p}\) ;  Initialize list PLANTS with vertices \(MPR,\ldots,p\) in increasing order of \(\mathcal{X}_{p}\); \(i\leftarrow\mathit{FIRST}(\mathit{VERITICES})\); while\(i\
eq\mathbf{nil}\)do /* Try to connect \(i\) to an existing subtree or plant */  Sort vertices \(j\) in ASSIGNED in increasing order of \(c_{ij}\); \(j\leftarrow\mathit{FIRST}(\mathit{ASSIGNED})\); while\(j\
eq\mathbf{nil}\)and\(a(i)==0\)do \(k\gets a(j)\); if\(k\in V_{c}\) and \(s(k)\geq d_{i}\) and \(s(r(k))\geq d_{i}\)then \(a(i)\gets k\); \(s(k)\gets s(k)-d_{i}\); \(r(i)\gets k\); \(s(r(k))\gets s(r(k))-d_{i}\);  end if if\(k\in V_{p}\) and \(s(k)\geq d_{i}\)then \(a(i)\gets i\); \(s(i)\gets s(i)-d_{i}\); \(r(i)\gets k\); \(s(k)\gets s(k)-d_{i}\);  end if if\(a(i)\
eq 0\)then  Remove \(i\) from CANDIDATE list;  Add \(i\) to ASSIGNED list;  end if \(j\leftarrow\textsc{NEXT}(\textsc{ASSIGNED})\);  end if if\(a(i)==0\)then /* Open a new plant an connect vertex \(i\) */ \(k\leftarrow\mathit{FIRST}(\textsc{PLANTS})\); \(a(i)\gets i\); \(s(i)\gets s(i)-d_{i}\); \(s(k)\gets s(k)-d_{i}\);  Remove \(i\) from CANDIDATE list;  Add \(i\) to ASSIGNED list;  Remove \(k\) from PLANTS list;  Add \(k\) to ASSIGNED list;  end if  end if \(i\leftarrow\textsc{NEXT}(\textsc{VERITICES})\);  end if return
```  
**Algorithm 1**Pseudo-code for cost-based assignment decoder