Compact formulations of the Steiner Traveling Salesman Problem and related problems

► Most papers on the TSP assume that the graph is complete. ► The Steiner TSP is a variant of the TSP defined on general graphs. ► The existing integer programming formulation has an exponential number of constraints. ► We present several formulations that are of polynomial size. ► We also present similar compact formulations for some related problems.