Various neural network models have been proposed to tackle combinatorial
optimization problems such as the travelling salesman problem (TSP). Existing
learning-based TSP methods adopt a simple setting that the training and testing
data are independent and identically distributed. However, the existing
literature fails to solve TSP instances when training and testing data have
different distributions. Concretely, we find that different training and
testing distribution will result in more difficult TSP instances, i.e., the
solution obtained by the model has a large gap from the optimal solution. To
tackle this problem, in this work, we study learning-based TSP methods when
training and testing data have different distributions using adaptive-hardness,
i.e., how difficult a TSP instance can be for a solver. This problem is
challenging because it is non-trivial to (1) define hardness measurement
quantitatively; (2) efficiently and continuously generate sufficiently hard TSP
instances upon model training; (3) fully utilize instances with different
levels of hardness to learn a more powerful TSP solver. To solve these
challenges, we first propose a principled hardness measurement to quantify the
hardness of TSP instances. Then, we propose a hardness-adaptive generator to
generate instances with different hardness. We further propose a curriculum
learner fully utilizing these instances to train the TSP solver. Experiments
show that our hardness-adaptive generator can generate instances ten times
harder than the existing methods, and our proposed method achieves significant
improvement over state-of-the-art models in terms of the optimality gap.

本文研究了使用自适应难度方法的基于学习的旅行商问题方法，通过定义硬度测量，使用硬度自适应生成器生成不同难度的实例，再利用课程学习器完全利用这些实例来训练 TSP 求解器。实验结果表明，我们的硬度自适应生成器可以生成比现有方法更困难的实例，而我们提出的方法在最优性差距方面显著优于最先进的模型。