Distance-Aware Attention Reshaping for Enhancing Generalization of Neural Solvers.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Neural solvers (NSs) using attention mechanisms excel at routing problems like the traveling salesman problem (TSP) and vehicle routing problem (VRP).
• Existing NSs exhibit attention score dispersion during generalization, leading to performance degradation.

Purpose of the Study:

• To enhance the generalization capabilities of neural solvers for routing problems.
• To address the issue of attention score dispersion in neural network-based solvers.

Main Methods:

• Proposes a novel distance-aware attention reshaping (DAR) method.
• Adjusts attention scores using inter-node distance information without increasing neural network parameters.
• Aims to improve the ability of NSs trained on smaller datasets to solve larger, differently distributed problems.

Main Results:

• The DAR method theoretically and empirically demonstrates effectiveness in improving NS generalization.
• Extensive experiments show advantages across various routing problems: TSP, ATSP, CVRP, VRPTW, CARP, and KP.
• The method enables NSs to make more rational choices on large-scale instances.

Conclusions:

• DAR is an effective technique for enhancing the generalization performance of neural solvers in combinatorial optimization.
• The method offers a parameter-free approach to improve attention mechanisms in neural networks for complex problem-solving.
• The study validates DAR's utility across a wide range of NP-hard problems.