Column generation for TSP

Question

For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach.

In the academic literature, an approach is proposed (for example here), where columns are either $1$-trees or $2$-matchings. I don't find this approach very intuitive for teaching (but maybe I need to re-read it !).

For the Vehicle Routing Problem, which obviously generalizes the TSP, there is the following classical (?) formulation :

Let $V$ be the set of nodes. Let $R$ be the set of feasible routes (vehicles are assumed identical). Let $y_r$ be a binary variable that takes value $1$ if and only if route $r \in R$ with cost $c_r$ is selected. So you want to minimize $$ \sum_{r\in R} c_r y_r $$ subject to

1. Each node $v$ is visited exactly once : $$ \sum_{r \in R \mid v \in r} y_r = 1 \quad \forall v \in V $$
2. You cannot use more than say $k$ vehicles : $$ \sum_{r \in R } y_r \le k $$

This formulation is very intuitive. When relaxing the binary variables, you have your master problem. And your subproblem boils down to finding routes/columns/paths with minimum cost based on the duals of the solved relaxed master problem.

What I find hard to explain is that this formulation is no longer relevant (or is it ?) if you only have $1$ vehicle (in other words if you are solving the TSP). In this case, the formulation becomes :

$$ \min \quad \sum_{r\in R} c_r y_r $$ subject to \begin{align} \sum_{r \in R \mid v \in r} y_r &= 1 \quad \forall v \in V \\ \sum_{r \in R } y_r &= 1 \end{align}

In this case a feasible route is a tour is visiting all nodes. And so the first constraint becomes useless and the master problem becomes equivalent to selecting the column with minimum cost. The whole problem is basically left to the sub-problem, where you need to find a Hamiltonian path with minimum cost.

So here are my questions :

1. Am I correct to say that the VRP formulation is not relevant for the TSP ?
2. Is there a similar approach that would work for the TSP ?
3. Do you think the first approach (where columns are $1$-trees or $2$-matchings) is a good one (for teaching purposes primarily)?

Answer 1

As Marco briefly explained in his comment, TSP is not the ideal problem to teach the column generation approach. TSP is suited for the row generation approach, also known as branch-and-cut, by following the Dantzig–Fulkerson–Johnson formulation that you can easily find on the web (for example, on the Wikipedia page related to TSP).

On the other, VRP is a good candidate to teach the column generation approach. You can start from the basics and go further and further in sophistication. Nevertheless, cutting stock problems and bin packing problems are maybe better candidates to start your lesson. Indeed, in the case of cutting stock, the subproblem (also called pricing problem) is simply a knapsack problem. In addition, studying the cutting stock problem allows an interesting historical note about the pioneering work by Gilmore and Gomory about column generation in the sixties (additional references are given in the Wikipedia page previously mentioned).

Answer 2

As in some of the other answers, using the TSP to teach column generation is perhaps not your best choice, since the columns are abstract mathematical structures (e.g. matchings) which are not as intuitive as for instance the columns (routes) in a CG for VRP.

If you insist on using the TSP as your CG example, the following document might be helpful as it provides a short read on a Branch-and-Price formulation for the TSP using perfect matchings: http://coin-or.github.io/jorlib/manual/manual.pdf, see Section 4 Example 3 - Solving the Traveling Salesman Problem through Branch-and-Price, page 18.

This manual provides a small graphical example, the master problem formulation, corresponding pricing problem, as well as a potential branching rule. Corresponding implementation can be found under https://github.com/coin-or/jorlib/tree/development/jorlib-demo/src/main/java/org/jorlib/demo/frameworks/columngeneration/tspbap