# Column generation for TSP

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)?
• 1. correct; 2. depends on "similar", the 1-trees model is in some sense "similar", however I totally agree on "not so intuitive" or "not so suited for colgen"; that partially answers 3. In my perception, TSP is not an ideal approach to teach the colgen idea, because colgen is not only about the algorithm but also about the "new" modeling opportunities you obtain (like pattern or coficuration based models). Just my 50 cent. – Marco Lübbecke Jan 18 '20 at 13:38