论文标题
图形旅行推销员问题的新整数编程公式
A New Integer Programming Formulation of the Graphical Traveling Salesman Problem
论文作者
论文摘要
在旅行推销员问题（TSP）中，推销员想参观一套城市并返回家园。从城市$ i $到城市$ j $旅行的费用是$ c_ {ij} $，这在对称TSP的任一方向上都是相同的。目的是准确访问每个城市一次，以最大程度地减少总旅行成本。在图形TSP中，可以多次访问城市，这在稀疏图上可能是必要的。我们为图形TSP提供了一种新的整数编程公式，仅需要两类的约束，这些约束在数字上是多项式或多项式可分离的，同时解决了Denis Naddef提出的一个开放问题。
In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost $c_{ij}$ of traveling from city $i$ to city $j$, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classes of constraints that are either polynomial in number or polynomially separable, while addressing an open question proposed by Denis Naddef.
