The applet shows cities as black squares, identified by distinct numbers. The traveling salesman problem (TSP) is to find a shortest tour through each of the cities.

In the examples, only certain edges, that is, direct connections between pairs of cities, are permitted in the tour; they are the white lines in the applet drawing. We can describe a tour by assigning to each edge a value of 0 or 1, with 1 meaning the edge is in the tour.

In a linear programming (LP) relaxation of the TSP, we assign to each edge a value between 0 and 1 (fractional values are allowed), and initially we only require that at each city the sum of values assigned to the edges joined to the city is exactly two. (This is of course satisfied by all tours!). To display the optimal LP solution, click on the "Solve Problem" button.

The values the LP solution assigns to the edges are color-coded according to the following scheme.

The optimal value of the LP relaxation is a lower bound for the TSP, that is, if the LP value is 100, then no tour can have length less than 100. In the applet, the LP optimal value is given just above the window containing the exact values of the edge assignments.

With lower bounds, the bigger the number the better (since we get more information about the possible length of a tour). To improve the LP lower bound, the assignment of values to edges can be restricted by adding more requirements (as long as we know that these requirements are satisfied by all tours).

A basic property of all tours is that for any collection S of cities (other than the entire collection), a tour must include at least 2 of the edges joining cities in S to cities not in S (otherwise the salesman gets stuck in S). Therefore, we can add the condition in the LP relaxation that the sum of the values assigned to the edges joining S to cities not in S must be at least 2; this is called a subtour-elimination constraint.

Unfortunately, there are very many subtour-elimination constraints and we cannot simply add them all to the LP relaxation. Instead, the cutting-plane method just adds the constraints as they are needed. In the applet, this can be done by first clicking on the cities S (or typing them into the space next to "Add Subtour Inequality") then clicking on the "Add Subtour Inequality" button.

After one or more constraints have been added to the LP relaxation, clicking on the "Solve Problem" button will display a new LP optimal solution. If the LP solution does not change, then the subtour-elimination constraints that were added were already satisfied by the existing LP solution.

In the beginning it should be easy to spot sets S that lead to subtour-elimination constraints that are violated, that is, constraints not satisfied by the current LP solution. For example, any "island" of cities will work, or any set of cities that is connected only by a single edge to the remaining cities. After these easy cases are handled, closer inspection can often turn up additional violated constraints, but it may take some searching to spot the correct sets of cities.

On some examples, you can eventually get the LP solution to be a tour, and therefore solve the TSP! This is not always possible, but you will still end up with a very good lower bound and also an LP solution that can serve as a guide in trying to find a good tour. For typical geometric TSP instances, the difference between the best tour and the best LP lower bound is less than 1%, so you can indeed obtain very good approximations to optimal TSP solutions.