# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Problems
#### 3.2.1 Integer Linear Programming  
ILP is a general form for many discrete COPs and is of great practical significance. Table 5 presents ML methods proposed in recent years to solve the ILPs.  
To solve MILP problems, B&B is a common approach, which builds an optimization tree and selects variables for branching at each step, and prunes according to the results of LP-relaxation. In the branching stage, strong branching (SB) gives the score of candidate nodes to guide the selection. [PERSON] et al. [70] proposed to treat the scoring stage of SB as a regression problem and used supervised learning for fitting to solve binary MILP problems. The method effectively improves operation efficiency. [PERSON] et al. [71] formally modeled the decision process of B&B as MDP, and treated node selection and node pruning as classification problems. They set the label of expand and prune according to whether the node is optimal, and then used the imitation learning method to deal with the problem of imperfect information. On larger-scale problems, the method of [PERSON] et al. further reduces the computational time and the gap with the optimal solution on MILP problems. [PERSON] et al. [72] further regarded the SB scoring problem as a learning-to-rank problem where nodes are labeled by binary ranking, that is, nodes with scores close to the highest score are ranked higher than others. The ranking strategy is learned by supervised learning methods. In addition, the method proposed by [PERSON] et al. seamlessly transfers the branching strategy from the SB- to ML-based method when applied to a given problem, instead of learning the strategy offline. [PERSON] et al. [93] also formulated B&B as MDP and learned the policy by behavioral cloning. They treated the binary tree as a bipartite graph and used GCNN to encode the state to improve the generalization ability of the algorithm on test instances.  
The work of [PERSON] et al. [251] concerned the issue of the decomposition of MIPs. A MIP problem can be decomposed in many ways, and some of them can well reflect the structure of the original model for which the MIP can be reformulated to an easier form to solve, while some decompositions are not suitable. [PERSON] et al. proposed to use supervised learning to train a classifier to decide whether a given decomposition of MIP is worth continuing to be reformulated. [PERSON] et al. tested the classifier on both structured instances (such as set covering, BPP, VRP, etc.) and unstructured instances with a total of 1619 decompositions.  
[PERSON] et al. [84] directly used the mathematical gradient substitution method to enable the loss between the objective function and the optimal objective function to be passed to the parameters \(c\) of cost function and the parameters \(A\) and \(b\) of the constraints, thereby realizing an end-to-end black-box solver. [PERSON] et al. showed high accuracy of this method on very small-scale ILP problems.  
[PERSON] et al. [94] used reinforcement learning to improve the cutting plane method (specifically, [PERSON]'s method [252]) for solving IPs. [PERSON] et al. modeled the process of selecting cutting planes as an MDP, where the state is the current feasible region and the reward is the change in the value of the objective function between episodes. In order to deal with the problem that the policy is independent of the order of the constraint parameters and the input length is variable, [PERSON] et al. used the attention network and LSTM, respectively. In the experiment, [PERSON] et al. considered problems of three scales with the number of variables, and the number of constraints being about 200, 1000, and 5000.