2012/03/17 by Adam N. Letchford, Letchford, Adam N., Saeideh D. Nasiri +3 · 2 citations
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.OC
paper · pdf · doi:10.48550/arxiv.1203.3854
submitted to EJOR
arxiv created 2012/03/17 · arxiv updated 2012/03/20
The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there exist several known \em compact formulations of the TSP, i.e., formulations with a polynomial number of both variables and constraints. In this paper, we show that some of these compact formulations can be adapted to the STSP. We also briefly discuss the adaptation of our formulations to some closely-related problems.