Step 9: Still a solution with 0's, 1's, and 1/2's, with two large regions joined by a single edge assigned the value 1.
Either of the two regions gives a violated subtour-elimination constraint; we will use the bottom region (it has fewer cities) and not include city 12, since it is only joined to the rest of the bottom by two red edges.
The set S in this case consists of the cities 0 through 11.
|
