# Learning-Based Branching Acceleration for Unit Commitment with Few Training Samples
## 3 Branch-and-Bound Algorithm  
This section provides a detailed introduction to the B&B algorithm. As one of the fundamental algorithms for obtaining global optimal solutions to MILP problems [30], the B&B algorithm is extensively applied to the UC problem in power systems. Its key concept involves constructing a search tree to systematically enumerate feasible solutions that could potentially be the global optimum. Through branching and pruning operations, the upper bound (current optimal feasible solution) and lower bound (current optimal linear relaxed solution) of the problem are dynamically updated. The global optimal solution is identified when the gap between these bounds is less than the predefined value. The search process of the B&B algorithm consists of three main components, which are 1. Branch selection policy: By assessing the significance of discrete candidate variables, branches are generated to further partition the feasible region, thereby reducing the number of generated nodes. 2. Node selection policy: Determine the exploration order of unexplored nodes to guide the B&B algorithm in identifying the node corresponding to the global optimal solution. 3. Pruning policy: Deciding whether a node should be further explored can effectively minimize the size of the search tree. To aid in understanding the algorithm, this paper first defines some symbols. Each node of the B&B search tree contains an MILP relaxed problem (linear programming problem). Let \(N_{n}\) be the \(n\)-th node and \(W_{n}\) be the relaxed problem at that node. The number of variables in the problem variable \(X\) is denoted as \(J\), and the ordinal numbers of all the discrete variables are stored in \(A\). The original problem variable feasible domain \(\partial=\{x:x[a]\in\{0,1\},\forall a\in A\}\) is relaxed to \(\wp=\{x:x[a]\in[0,1],\forall a\in A\}\) and \(x[a]\) is the \(a\)-th problem variable. It follows that the objective function of the original problem and the objective function of the relaxed problem are \(\min\{f(x):x\in\partial\}\) and \(\min\{f(x):x\in\wp\}\), respectively. Let the optimal solution and objective function values of the relaxed problem at node \(N_{n}\) be \(x_{n}^{*}\) and \(v_{n}^{*}\), respectively,  
\[x_{n}^{*}=\arg\min\{f(x):x\in\wp\}, \tag{11}\]  
\[v_{n}^{*}=\min\{f(x):x\in\wp\}. \tag{12}\]  
In this paper, we use \(x_{n}^{*}[j]\) to denote the value of the \(j\)-th variable in \(x_{n}^{*}\), \(\forall j\in J\), and set \(c^{*}\) as the best integer solution found during the iterative solving process of the B&B search tree. The B&B algorithm maintains an unexplored node relaxed problem list \(\Psi\), and this list only contains the root node relaxed problem \(W_{1}\) at the beginning. In each iteration, the node selection policy is first used to pop a relaxed problem from \(\Psi\) to solve it and obtain its \(x_{n}^{*}\) and \(v_{n}^{*}\). Then, the pruning policy decides the following action of the node based on the obtained \(x_{n}^{*}\) and \(v_{n}^{*}\). If the policy decides to prune, the node does not need to be branched, and the algorithm proceeds to the next iteration. Otherwise, the node is preserved, and the branch selection policy evaluates the importance of the discrete variables in the original problem. If the most important discrete variable is indexed as \(a\), the feasible domain of \(x_{n}\) will be divided into two parts for branching as follows  
\[\wp_{n}^{1}=\wp_{n}\cap\{x:x[a]\leq\lfloor x_{n}^{*}[a]\rfloor\}, \tag{13}\]  
\[\wp_{n}^{2}=\wp_{n}\cap\{x:x[a]\geq\lceil x_{n}^{*}[a]\rceil\}, \tag{14}\]  
where \(\wp_{n}^{1}\) and \(\wp_{n}^{2}\) represent the feasible domains of the two new nodes \(N_{n}^{1}\) and \(N_{n}^{2}\), respectively, after the branching of the node \(N_{n}\). \(\lfloor x_{n}^{*}[a]\rfloor\) and \(\lceil x_{n}^{*}[a]\rceil\) are the values of the \(a\)-th variable of the node to be rounded upward and downward, respectively, which are set to 1 and 0 in this paper.