Neural Improvement Heuristics for Graph Combinatorial Optimization Problems.

Area of Science:

• Graph Neural Networks
• Combinatorial Optimization
• Machine Learning

Background:

• Recent advancements in Graph Neural Network (GNN) architectures and computational power have significantly impacted combinatorial optimization (CO).
• Neural Improvement (NI) models are successful for CO but are limited to node-feature-based problems, excluding edge-encoded information.
• Existing NI models struggle with graph-based problems where crucial data resides in edges, not just nodes.

Purpose of the Study:

• To introduce a novel Neural Improvement (NI) model for graph-based combinatorial optimization problems.
• To develop an NI model capable of utilizing information encoded in nodes, edges, or both.
• To enhance hill-climbing algorithms by guiding neighborhood operation selection.

Main Methods:

• Developed a novel Neural Improvement (NI) model for graph neural networks (GNNs).
• Integrated node and edge information processing within the NI framework.
• Applied the model as a component in hill-climbing algorithms for combinatorial optimization.

Main Results:

• The proposed NI model achieved 99th percentile performance for the preference ranking problem (PRP).
• Demonstrated superior performance over conventional methods in recommending neighborhood operations.
• Achieved 98th percentile for the traveling salesman problem and 97th percentile for the graph partitioning problem (GPP).

Conclusions:

• The novel NI model effectively handles graph-based problems with node and/or edge information.
• This approach significantly improves performance in combinatorial optimization tasks.
• The model offers a versatile solution for problems like PRP, TSP, and GPP.