A New Integer Programming Formulation of the Graphical Traveling Salesman Problem

Autor:	Carr, Robert D., Simonetti, Neil
Rok vydání:	2020
Předmět:	Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms G.2.2
Druh dokumentu:	Working Paper
Popis:	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. Comment: 19 pages, only one figure from an external image
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2006.04933 Zobrazit plný text záznamu View this record from Arxiv