  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.

Optimization and Control;Discrete Mathematics