Finding the Exact Integrality Gap for Small Traveling Salesman Problems
Finding the Exact Integrality Gap for Small Traveling Salesman Problems
复制标题
寻找小型旅行商问题的精确积分差距
DOI：
--
复制
发表时间：
2002
影响因子：
1.7
通讯作者：
Sylvia C. Boyd
中科院分区：
文献类型：
--
作者：
Geneviève Benoit;Sylvia C. Boyd
对称旅行商问题（STSP）是在n个结点的加权完全图中寻找一个最小权Hamilton圈。一个方向，似乎有希望找到改进的解决方案的STSP是一个线性松弛的研究这个问题，称为subtour消除问题（SEP）。组合优化中的一个著名猜想是，在度量情形下，SEP的完整性间隙为4/3。找到这个完整性差距的确切值是具有挑战性的，即使对于小的n值，因为它是很难建模的方式，可以实际解决这个问题。我们描述了我们是如何能够克服这些困难，并获得确切的完整性差距的所有值的n到10和下限为这个差距的所有值的n从11到14。我们的结果产生了一个新的更强的形式的猜想，这是依赖于n。
The symmetric traveling salesman problem (STSP) is to find a minimum weight Hamiltonian cycle in a weighted complete graph on n nodes. One direction which seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the subtour elimination problem (SEP). A well-known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Finding the exact value for this integrality gap is challenging even for small values of n as it is difficult to model this problem in a way that can be solved practically. We describe how we are able to overcome such difficulties and obtain the exact integrality gap for all values of n up to 10 and a lower bound for this gap for all values of n from 11 to 14. Our results give rise to a new stronger form of the conjecture which is dependent on n.