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困难还是多项式时间算法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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.