Step 7: The LP solution consists of two regions joined by a single long path (so the salesman can get from one region to the other, but has no return route).
We will add the subtour-elimination constraint for the bottom region (the one bordered by the 5-cycle of red edges).
The set S in this case is (2 3 4 6 7 8).
|
