# Improved Branch-and-Bound Antenna Selection Algorithm for Massive MIMO
## 3 Efficient Antenna Selection via Enhanced Branch-and-Bound Optimization
### Branch-and-Bound Antenna Selection
The antenna index selected at the \(k_{l+1}\)th step can be found by the following expression:

\[K_{l+1}=\mathrm{argmin}_{k\in Y_{l+1}}\ \alpha_{k_{l+1},\ l+1}, \tag{17}\]

where \(Y_{l+1}\) denotes the candidate antenna set at step \(l+1\), \(Y_{l+1}=Y_{l}\backslash K_{l}\); \(K_{l}\) serves as the index for the antenna selected for elimination at step \(l\). Certainly, the aforementioned derivations were conducted under the condition that the specific value of \(d\), representing the optimal antenna subset size, is predetermined. The I-BAB algorithm proposed in this paper differs from the conventional BAB algorithm in that the size of the optimal antenna subset can be defined as a range rather than a specific value. Specifically, we assign \(MAX\) as the maximum threshold and \(MIN\) as the minimum threshold for the optimal antenna subset size \(\mid S_{opt}\mid\). Therefore, when identifying the antenna index selected in step \(l+1\) of the algorithm, we observe non-uniqueness in the index determination, such that: \(K_{l+1}=\arg_{k_{l+1}\in Y_{l+1}}\alpha_{k_{l+1},\,l+1}\). Let \(S\) denote the set of \(N_{r}\) receiving antennas, which corresponds to all rows of the channel matrix \(\mathbf{H}\), \(S=\{1,\,2,\,\cdots,\,N_{r}\}\), \(F=S\), then push \(F\) into the stack as the root node. Let \(d\) denote the cardinality of the optimal antenna subset currently under search (\(MAX\geq d\geq MIN\)), which undergoes a gradual decrement from \(MAX\) to \(MIN\). The implementation steps of the proposed I-BAB algorithm are as follows:

1. Pruning Operation: If the channel capacity of the current node \(C_{current}\) is less than \(C_{opt,\,d}\) (where \(C_{opt,\,d}\) represents the historical optimal value corresponding to \(d\)), the generation of child nodes for the current node is terminated. This constitutes the critical mechanism of the pruning operation. 2. Generation of Child Nodes: The number of child nodes \(m\) for the current node can be calculated using the following formula: \[m=\text{current-node}.t-(n-d-\text{current-node}.l-1).\] (18)

In Equation (18), \(t\) represents the size of the current candidate antenna subset; \(n\) denotes the cardinality of the complete receiving antenna set, i.e., \(n=N_{r};l\) indicates the level of the current node in the search tree, initialized as \(l=0\). Specifically, for each current node, all possible subsets are generated by removing individual antennas one at a time, followed by calculating the corresponding capacity degradation \(\Delta_{i}\) for each subset (\(i=1,\,2,\,\cdots,\,N_{r}\)); after sorting \(\Delta_{i}\) in ascending order, the top-\(m\)\(\Delta_{j}\) (\(j=1,\,2,\,\cdots,\,m\)) with minimal descent values are selected. Subsequently, the corresponding subset \(S_{child,\,j}\) associated with each chosen \(\Delta_{j}\) is designated as child nodes. 3. Reverse Stack Pushing: In conventional stack-based algorithms, child nodes are pushed into the stack in the order of \(S_{child,\,1}\), \(S_{child,\,2}\), \(\cdots\), \(S_{child,\,m}\). However, the I-BAB algorithm implements a critical modification where child nodes are instead inserted in the reverse order \(S_{child,\,m}\), \(S_{child,\,m-1}\), \(\cdots\), \(S_{child,\,1}\). This pivotal procedural adjustment facilitates substantial pruning operations in subsequent computations, thereby effectively reducing algorithmic complexity. 4. Update Optimal Solution: When the current subset size \(\mid S_{current}\mid=d\), update \(S_{opt,\,d}=S_{current}\), \(C_{opt,\,d}=C_{current}\); \(d\) is updated to the subsequent value within the specified constraint range. Then repeat the above steps. 5. Termination Criterion: The search terminates upon stack emptiness. 6. Output: Sequentially output the corresponding \(S_{opt,\,d}\) and \(C_{opt,\,d}\) for each \(d\) (\(MAX\geq d\geq MIN\)). The detailed algorithmic workflow of I-BAB is comprehensively outlined in Algorithm 2.