Optimization Online


Compact formulations of the Steiner traveling salesman problem and related problems

Adam Letchford (A.N.Letchford***at***lancaster.ac.uk)
Saeideh Nasiri (s.d.nasiri***at***lancaster.ac.uk)
Dirk Theis (theis***at***ovgu.de)

Abstract: 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.

Keywords: traveling salesman problem, integer programming, extended formulations

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: A.N. Letchford, S.D. Nasiri & D.O. Theis (2013) Compact formulations of the Steiner TSP and related problems. Eur. J. Oper. Res., 228, 83-92.


Entry Submitted: 03/16/2012
Entry Accepted: 03/17/2012
Entry Last Modified: 11/05/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society