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-HARD还是具有多项式时间算法。该奖项反映了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.