Relationship between k-cutsets and comb inequalities

The TSP is the problem of finding a single cycle going through all the vertices of a graph suchthat the sum of the costs of the edges it contains is minimal. It has many applications andhas been motivated by concrete problems, such as school bus routes, logistics, routing, etc. Itis solved in CP with the WCC [2] and the k-cutset constraint [4]. The TSP can also be solvedby the MIP dedicated solver Concorde [1] which uses an LP model in combination with thecutting-plane method. The CP and MIP use structural constraints for their solving. In thisarticle, we show that the formulations look very different but they are in fact very similar.