Given an undirected graph with edge costs and both revenues and weights on the vertices, the Traveling Salesman Subtour Problem is to find a subtour that passes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. This problem generalizes the Traveling Salesman Problem and is therefore -hard. The Traveling Salesman Subtour Problem and its relatives are of interest in themselves, and they also arise as subproblems in various contexts.

We present a new and strong formulation, which is inspired by the classic side-constrained 1-tree formulation of the Traveling Salesman Problem. Here, the side constraints comprise vertex degree restrictions, a knapsack constraint and variable upper bound (VUB) constraints. In our solution approaches, these side constraints are Lagrangian relaxed. The relaxed problem is transformed, via a simple variable substitution, into the problem of finding a minimum cost degree-constrained 1-tree in an expanded graph.

The Lagrangian dual problem is attacked with subgradient optimization and a cutting plane scheme. The latter is implemented in its dually equivalent form, that is, as a column generation scheme. The column generation procedure is stabilized by restricting the dual variables to stay inside a box around the current dual iterate; this technique is a slight modification of the so called boxstep method. Further, a combined algorithm is presented. This combination inherits the advantages of subgradient optimization and column generation, and it aims to avoid their respective drawbacks.

An important conclusion from our work is that the use of the VUB constraints significantly improves the quality of the lower bounds, although they are redundant in the integer programming formulation. We also conclude that the stabilizing technique is crucial for obtaining computational efficiency in the column generation scheme. Finally, it is established that it might be very advantageous to use the subgradient optimization procedure as a means for initiating the column generation scheme.