# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Methods
#### Sequence2 Vector
tried three kinds of search methods and compared them: greedy search (greedily selecting the next node from its neighbors with the highest probability), beam search (expanding the \(b\) most probable edge connections among the node's neighbors), and beam search with shortest tour heuristic (selecting the shortest tour among the set of \(b\) complete tours as the final solution at the end of beam search). Experiments show that \begin{table}
\begin{tabular}{c c c} \hline \hline
**Reference** & **Year** & **Advantage or Novelty** \\ \hline [PERSON] et al. [81] & 2017 & encode source and target graphs \\ [PERSON] et al. [82] & 2017 & just encode source graph \\ [PERSON] et al. [230] & 2018 & model SAT as an undirected graph \\ [PERSON] et al. [231] & 2018 & solve SAT, MIS, MVC and MC \\  & & with GNNs \\ [PERSON] et al. [232] & 2019 & solve graph coloring problem \\  & & (GCP) with GNNs \\ [PERSON] et al. [233] & 2019 & solve problems involving \\  & & numerical information \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Supervised learning methods using graph neural networks. for TSP problems with a fixed number of nodes, the quality of the solution outperforms previous DL approaches. [PERSON] et al. [230] solved the satisfiability (SAT) problem with GNNs [78; 234]. Due to the permutation invariance and negation invariance properties of SAT, [PERSON] et al. modeled SAT as an undirected graph with one node for every literal and clause, one edge between each literal and clause, and one edge between literal and complementary literal. Then, the message-passing method [235] is used to update the embedding of each node, and the resulting embeddings are fed into MLP to obtain the literals' votes, which are then used to calculate the loss with the true label. The model parameters of [230] are independent of the problem size due to two aggregation operators: to form the incoming message by summing the messages of one node's neighbors, and to form the logit probability by calculating the mean of literal votes. Similar to [230], [PERSON] et al. [232] solved the graph coloring problem (GCP) (the graph coloring problem (GCP): does a graph G accept a C-coloring?) with GNNs [78; 80; 232]. They took the vertex-to-color adjacency matrix as input, and finally used MLP to obtain the logit probability and calculated the loss with true labels. [PERSON] et al. [230] and [PERSON] et al. [232] successfully solved some NP-hard problems involving symbolic relationships (e.g., whether an edge is connected), and [PERSON] et al. [233] further applied GNNs [79] to solve the NP-hard problems involving numerical information (in this paper, they focused on a variant of TSP: does graph G admit a Hamiltonian path with cost \(<~{}C\)?). In order to encode the weights of edges, [PERSON] et al. used a vertex-edge adjacency matrix as input, and represented an edge using the concatenation of weight and \(C\), which is a 2-d vector \(\in~{}\mathbb{R}^{2}\). Then, similar to [230; 232], the refined edge embeddings are fed into an MLP to compute the logit probability. [PERSON] et al. [231] solved four NP-hard problems with GCN [236; 237]: SAT, MIS, MVC and MC. Taking MIS as an example, the graph is presented by an \(N\times N\) binary adjacency matrix, and then mapped to an \(N\)-dimensional real-valued vector through GCN, indicating how likely each vertex is to belong to the MIS. Finally, the solution is obtained from this real-valued vector. A basic method to obtain it is greedy search using the vector as the heuristic function. However, [PERSON] et al. pointed out that this search method can become confused when there are multiple optimal solutions for the same graph. Therefore, a further improvement is using GCN to generate multiple probability maps, which is integrated into the tree search procedure (breadth-first account for the diversity of solutions).