This implementation is about as basic as it gets, but is hopefully “correct”. The branch-and-bound solver might not be, and is certainly not very efficient.
From the Georgia Institue of Technology website:
Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and returning to your starting point. In the standard version we study, the travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X.
Given our definition of a TSP from above, we can start formulating the problem as an integer program:
where our xij is a binary (0 or 1) variable that says if we will go from city i to city j on our tour. We are dealing with just the case where the costs between cities are symmetric, that is cij = cji, so this can be simplified considerably. The simplified IP for a 4 city problem would have:
So now we’ve got our integer programming formulation, let’s try it out on a problem. Click the Reset button below - the default configuration of cities should (magically) appear.
You can drag the cities around and re-solve, or add cities to make it more complex. When you are ready to move on, click the Reset button.
You may notice that the solution is not quite right for certain arrangements. While each city is visited and left, the optimal solution was not a path through all the cities but instead two smaller paths. We can call these smaller tours subtours, and the constraints necessary to eliminate them are called subtour-elimination constraints.
For a better and more detailed explanation of this, check out the Georgia Tech website.
To complete our integer programming formulation we need to add these subtour-elimination constraints. An example of a subtour elimination constraint for the 6 city problem shown above would be:
This says that no more than two of the arcs between the nodes (0,1,2) are allowed to be in the solution. Here is something to try: how many possible subtour-elimination constraints are there for this problem? The answer is big, and keeps getting bigger as the number of cities grows. It’d take a long time to just write out all those constraints, let alone solve it. And yet, people solve TSPs with integer programming - so whats the secret?
Lets try adding that subtour-elimination constraint we worked out before:
Have you followed the above instructions? Now re-solve the TSP above. Perfect!
We only need one of the many possible subtour-elimination constraints to change our nearly-correct solution into the optimal solution. A very similar method was first used quite some time ago, in 1954 to solve a problem with 49 cities! This way of solving a problem, by first solving a relaxed version of it and then adding constraints (or “cuts”) to improve the relaxation, is one of the techniques used to solve all sorts of integer programs.
We can see what the solver is doing by looking at the output that appears below when we hit “Solve”.