# Learning-Based Branching Acceleration for Unit Commitment with Few Training Samples
## 4 Branching Acceleration for Unit Commitment
### Enhanced Pruning Policy Based on Imitation Learning  
The tree search process of the B&B algorithm can be regarded as a sequential decision problem, which consists of the state space \(S\), the action space \(R\), and the policy space \(K\)[31]. The specific decision-making process can be briefly described as follows. For the node \(N_{n}\), the decision-making agent uses its policy \(\kappa\) to provide the optimal action \(r_{n}\) based on the observed state \(s_{n}\), i.e., \(\kappa(s_{n})=r_{n}\). The action \(r_{n}\) will have an impact on the next state \(s_{n+1}\) of the problem.  
Theoretically, if the features and labels of all nodes are known, strategies for such finite-dimensional sequential decision problems can be determined through supervised learning. However, in the UC problem, the large number of binary variables results in an excessively large training dataset and an overwhelming number of input features, significantly increasing the complexity of training and rendering this approach highly inefficient. If only some of these nodes are selected for training, and the model's performance cannot be guaranteed, it may lead to unsatisfactory results. To address the challenge, this paper adopts the data aggregation algorithm, dynamically collecting features and labels to reduce training complexity while ensuring performance [32]. This algorithm shifts the approach from supervised learning to the realm of imitation learning.  
The key idea of imitation learning is that learners can improve their performance by imitating the behavior of experts. Unlike supervised learning, which needs to prepare all features and labels before training, imitation learning collects features and labels for the learning object during the learning process, allowing for the correction of errors from the previous policy. This dynamic data collection method reduces the size of the training dataset and improves the training performance and efficiency.  
From Section 3, the computation time of the B&B algorithm is determined by the number of nodes explored in its search tree. Among the three policies, the pruning policy plays the most direct and effective role in controlling the number of nodes explored. The B&B algorithm adopts a conservative pruning policy to ensure global optimality by exhaustively checking and comparing all potential solutions. However, this policy results in a significant portion of the computation time being wasted on examining non-optimal nodes. Consequently, enhancing the original pruning policy can effectively reduce the algorithm's computational time and improve its efficiency.  
In this paper, we presented an enhanced pruning policy based on imitation learning. This policy utilizes imitation learning to learn the optimal pruning policy of the B&B algorithm. By integrating an additional policy model into the original pruning policy, it effectively prunes undetermined non-optimal nodes, substantially reducing the search tree size. Specifically, a neural network is employed as the classifier for the enhanced pruning policy. The learned policy \(\kappa\) takes the features of node \(N_{n}\) (\(s_{n}\)) as input and outputs the probabilities of different actions, thereby determining the action \(r_{n}\) to be taken, \(r_{n}\in\{\text{preserve, prune}\}\). Using a neural network as the classifier not only facilitates the application of the threshold iteration algorithm to ensure test feasibility but also dynamically balances computational performance with complexity. The specific design of the neural network is elaborated in Section 4.3.1.  
The objective of the enhanced pruning policy is to identify the global optimal solution with a minimal number of nodes, retaining only nodes on the search path to the optimal solution (i.e., the feasible domain contains only the optimal solution). These retained nodes are termed optimal nodes (\(N^{\text{opt}}\)) are shown as red-bordered nodes in Figure 1. The \(N^{\text{opt}}\) are labeled as class preserve, while all other nodes are labeled as class prune.