LG AI Research 253: Trends in Neural Combinatorial Optimization Research

Combinatorial Optimization (CO) is a field of mathematical optimization in which the set of feasible solutions is defined discretely. A representative example is the Traveling Salesman Problem (TSP), and many such problems fall into the category of NP-hard, meaning a solution cannot be guaranteed within polynomial time.

Recently, the field of Neural Combinatorial Optimization (NCO), which leverages deep learning to effectively solve such problems, has been actively researched. Existing studies have mainly experimented on small graphs with 100 or fewer nodes, but improving Scalability is essential for handling large-scale real-world data.

LeNSE is a methodology for efficiently solving combinatorial optimization problems on large-scale graphs. This model uses existing heuristic algorithms as they are, while aiming to find an efficient Subgraph that allows the solver to produce results quickly.

The core mechanisms of LeNSE are as follows:

• Discriminative Subgraph Representation: Uses GraphSAGE and a k-pooling layer to learn representations of subgraphs likely to contain the optimal solution. Here, InfoNCE loss is used to maximize the mutual information between samples.
• Subgraph Navigation: Uses Reinforcement Learning to modify a randomly initialized subgraph into a better subgraph, progressively finding the optimal solution.