13
$\begingroup$

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)?
$\endgroup$
1
  • 8
    $\begingroup$ 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. $\endgroup$ Jan 18 '20 at 13:38
8
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ Thanks @LocalSolver for you insight. Indeed, row generation seems to be much more appropriate. Usually, in math it is hard to generalize stuff, and easy to pick a special case and use the general formula/theorem/algorithm. I found it curious that in this case, selecting a specific case makes things go bad. I think also scheduling is appropriate for column generation, as the formulation is intuitive. $\endgroup$
    – Kuifje
    Oct 23 '20 at 16:49
  • $\begingroup$ @Kuifje, AFAIK, for scheduling problems, one of the best way to deal with that, is CP. $\endgroup$
    – A.Omidi
    Oct 23 '20 at 17:38
  • $\begingroup$ @A.Omidi I meant staff/employee scheduling (yetanothermathprogrammingconsultant.blogspot.com/2017/01/…) more than machine scheduling. $\endgroup$
    – Kuifje
    Oct 25 '20 at 7:57
  • $\begingroup$ Thanks for your comment, @A.Omidi, you're totally right. Indeed, another field where column generation is widely used is workforce planning and scheduling, especially in the airline industry with the famous crew scheduling problem. Here is the seminal paper (1988) by Desrochers and Soumis on this topic: link.springer.com/chapter/10.1007/978-3-642-85966-3_8. Nevertheless, for teaching, the cutting stock problem is maybe more appropriate. $\endgroup$ Oct 25 '20 at 8:08
  • $\begingroup$ @kuifje, many kinds of scheduling problems would be interpreted as a CP form. Also, combining CP and exact method to solve the real-world scheduling problem is very interesting. While ago I tried this and the results were very good. 🙂 $\endgroup$
    – A.Omidi
    Oct 25 '20 at 12:54
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.