旅行推销员问题是最古老的计算问题之一：“给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。”看起来简单，但求解十分困难。它被认为是一个 NP 完全问题。它的一种形式化方法是整数线性规划。60 多年以来研究人员提出多种解决整数线性规划的算法，但都比较慢，过去四十年改进甚微。普林斯顿高等研究院的 Victor Reis 和华盛顿大学的 Thomas Rothvoss 最近的工作实现了整数线性规划求解算法的最大速度提升，被认为代表了近 40 年来首次求解器的重大改进。他们通过组合了几何工具去限制可能的解决方案，创造了一种更快的算法。

https://www.quantamagazine.org/researchers-approach-new-speed-limit-for-seminal-problem-20240129/
https://arxiv.org/abs/2303.14605