AF: Small: Looking Under Rocks: A Search for a Provably Stronger TSP Relaxation

AF：小：寻找岩石下：寻找可证明更强的 TSP 弛豫

• 批准号: 1908517
• 负责人: David Williamson
• 金额: $ 10.56万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908517&HistoricalAwards=false
• 关键词: AF; Small; Looking; Under; Rocks

The traveling salesman problem is one of the most widely known problems of computational difficulty. The goal of the problem is to find the cheapest route for a salesman to visit a number of cities and return to home. It is not known whether there is a means of finding the best possible tour short of enumerating the exponentially large number of possible tours. Widely used algorithms for finding the best possible solution involve computing lower bounds on the length of the tour, and the closer the bound is to cost of the best possible tour, the quicker these algorithms run. This project will investigate alternative lower bounds for the traveling salesman problem to the ones widely used in practice, in the hopes of finding a provably better lower bound. A better understanding of lower bounds for the traveling salesman problem should help with solving other computationally difficult problems. The traveling salesman problem is one that is easy to explain to undergraduates and high school students. The PI and his graduate student plan to use their research as a means of outreach to such students, and to involve undergraduates in their project.Current methods for computing the optimal solution to the traveling salesman problem involve repeatedly solving a well-known linear programming relaxation of the problem. Although this bound is extremely good in practice (that is, it is very close to value of an optimal solution), its worst-case behavior is not well understood, despite decades of research. This project intends to study alternative lower bounds for the traveling salesman problem: it will start by studying semidefinite programming relaxations of the problem, and also consider other constraints that might be added to the linear program in order to be able to prove stronger statements about its worst-case behavior than are currently known. In addition, the project will consider some variants of the traveling salesman problem that have not been as well-studied, including the circulant TSP; for this variant, we are not even sure if the problem is NP-hard or has a polynomial-time algorithm.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

旅行商问题是最广为人知的计算难度问题之一。该问题的目标是为推销员找到访问多个城市并返回家乡的最便宜的路线。目前尚不清楚是否有一种方法可以在不枚举数量呈指数级增长的可能旅行的情况下找到最佳可能的旅行。用于寻找最佳可能解决方案的广泛使用的算法涉及计算旅行长度的下限，并且下限越接近最佳可能旅行的成本，这些算法运行得越快。该项目将研究旅行商问题的替代下界，以替代实践中广泛使用的下界，希望找到一个可证明更好的下界。更好地理解旅行商问题的下界应该有助于解决其他计算困难的问题。旅行商问题是一个很容易向本科生和高中生解释的问题。 PI 和他的研究生计划利用他们的研究作为接触这些学生的一种手段，并让本科生参与他们的项目。当前计算旅行商问题最优解的方法涉及重复求解著名的线性规划松弛的问题。尽管这个界限在实践中非常好（也就是说，它非常接近最优解决方案的值），但尽管经过了数十年的研究，它的最坏情况行为仍然没有得到很好的理解。该项目打算研究旅行商问题的替代下界：它将首先研究问题的半定规划松弛，并考虑可能添加到线性规划中的其他约束，以便能够证明关于其的更强的陈述比目前已知的最坏情况的行为。 此外，该项目还将考虑旅行商问题的一些尚未得到充分研究的变体，包括循环 TSP；对于这个变体，我们甚至不确定问题是 NP 难问题还是具有多项式时间算法。该奖项反映了 NSF 的法定使命，并且通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP

• DOI: 10.1016/j.orl.2020.02.011
• 发表时间: 2019-07
• 期刊: ArXiv
• 作者: Samuel C. Gutekunst;David P. Williamson

Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem

描述循环旅行商问题的 Subtour LP 的完整性差距

• DOI: 10.1137/19m1245840
• 发表时间: 2019
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Gutekunst, Samuel C.;Williamson, David P.
• 通讯作者: Williamson, David P.

Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps

旅行商问题的半定规划松弛及其完整性差距

• DOI: 10.1287/moor.2020.1100
• 发表时间: 2021
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Gutekunst, Samuel C.;Williamson, David P.
• 通讯作者: Williamson, David P.

The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem

旅行商问题半定松弛的无界积分间隙

• DOI: 10.1137/17m1154722
• 发表时间: 2018
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Gutekunst, Samuel C.;Williamson, David P.
• 通讯作者: Williamson, David P.