Start:   The initial LP solution for this example breaks up into three islands. That is bad news for the salesman, but it makes it easy to spot violated subtour-elimination constraints. We will begin by adding the constraint corresponding to the small triangle in the bottom left-hand-corner of the drawing. In this case, the set S consists of the three cities (0 1 5).

To add the subtour-elimination constraint for S, either click on the three cities, or type "0 1 5" in the text area to the right of the "Add Subtour Inequality" button. (See the figure below.) After selecting the three cities, click on "Add Subtour Inequality"; this will build the constraint and add it to the LP relaxation. (Note that we do not mean to click on the figure below; the figure is only a snap-shot of the applet. To actively follow along with the tutorial, you will need to open the applet in another browser window.)

Now click on "Solve Problem" to update the LP solution in the drawing.

To proceed to the next step in the tutorial, click on the Next link in the navigation table above.