The Concorde graphical user interface can be used to apply the Concorde TSP Solver to a specified set of cities. The Concorde solver uses the cutting-plane method, iteratively solving linear programming relaxations of the TSP. The interface shows the solver's progress at the end of each major iteration of cutting planes by coloring the edges according to their current LP values. Once the optimal tour is found it is shown by adding red edges to the display.
The time needed for the Concorde solver for a given instance can vary considerably with the number of cities and the complexity of the problem.
The Graphical User Interface implements in addition to the optimal Concorde solver the following edge generating algorithms:
Delaunay Triangulation,It also computes the following heuristic traveling salesman tours:
Minimum Spanning Tree, and
various Nearest Neighbor Set generators.
Greedy,
Boruvka, Quick Boruvka,
Nearest Neighbor,
Random, and
Chained Lin-Kernighan.
The Concorde interface can read and write graphs from and to files in various formats. (Note: Input graphs must have greater than 10 nodes.) Users may add, delete, and move a graph's vertices interactively. The interface consists of two display panes. One is used to show the graph, the other to print textual information about the graph, the algorithm's progress and results.
The Concorde interface is available for download via a windows setup script, see Downloads.
New book on the TSP to be published by Princeton University Press. Aimed at a general audience, the text provides everything you will need to join the attack on the salesman problem! To receive a note when the book is available (or just to show your support for Concorde and the TSP), please "Like" the In Pursuit of the Traveling Salesman. Facebook page. |