The simple fact we start with is clearly that x must be between 0 and 1. Then we have the degree constraints which say that there are exactly two arcs incident to each node. Same question: is this enough to describe the convex hull of tours? Well, the answer is positive only in very particular cases. It is so with no more than five nodes. Let's have a look at what happens with more than five nodes. For instance this is one vertex. All nodes have degree two, but we have two disjoint tours. This is another vertex: the red arcs have a value of one-half. With eight nodes we might find this other vertex. Certainly these three vertices are not tours. So, we will have to get rid of them by adding more inequalities to cut off these vertices. | ![]() |