Concorde iOS App Help

The Concorde App solves examples of the traveling salesman problem. Data sets are selected on the Load page. Tours and intermediate linear-programming solutions are displayed in the Plot view. For all instances, a log of the solution process is displayed in the Log view.


Selecting the algorithm

The algorithm to be run by the App is selected by tapping the gear symbol at the bottom of the screen. The choices available are the Exact Solver, Geometric Duality, and TSP Art. Select the one you want by tapping the button with the appropriate label.

If Geometric Duality is selected, then you can choose one of three modes, either Moats, Zones, or Penalties.

If TSP Art is selected, then you can choose one of three modes, either Grid, Swarm, or Lloyd's. The recommended mode is Grid to give a fast response, and either Swarm or Lloyd's to give possibly more interesting drawings (that may take a minute or two). The Size selection guides the algorithm in choosing the number of cities to use in the tour to represent an image. The recommended size is Medium.


Loading test data

Data sets are selected on the Load page. You can reach the page by tapping the Load button at the bottom of the screen.

When either the Exact Solver or Geometric Duality is the selected algorithm, there are three ways to select a data set: either use the slider to select the number of cities for a random geometric instance and tap the Create button, or enter the URL of a data file in TSPLIB format and tap the Load button, or select one of the three sample problems and tap the Read button.

When TSP Art is the selected algorithm, the load page will display menus listing the photos and images saved on the device. Select a photo or image to be drawn as a TSP tour in the spirt of the TSP Art work of Robert Bosch and Craig Kaplan. If there is a Web image you would like to select, first go to the Safari browser, tap the image, select Save Image, then return to the Concorde App.


Solving a problem

Once a data set is selected, the solution process is started by tapping the Run button in the bottom menu. This will happen automatically when TSP Art is the selected algorithm and an image is first loaded.

The solution process can be canceled by tapping the Stop button that appears in the bottom menu, although it may take a few seconds to stop the process.

You can move back and forth between the Plot view and the Log view of the solution process by tapping the corresponding buttons in the bottom menu.

In TSP Art mode, the generated tour is found with a heuristic algorithm. By tapping Run after the tour appears, the app will attempt to further improve the tour (and tapping Run can be repeated as often as you like). This should clean up any crossings that might appear in large instances.

Also in TSP Art mode, you can return to the Settings menu to select one of the other drawing algorithms (Grid, Swarm, of Lloyd's) and then tap Run to see an alternative rendering of the image as a tour.


Plot view

Exact Solver: Plot view

The LP solution assigns a value between 0 and 1 to each edge joining pairs of cities. The solution is displayed in the Plot view by coloring white the edges assigned value 0, coloring red the edges assigned 0.5, coloring black the edges assigned value 1, and taking colors from the spectrum for intermediate values.

Following the progress in the Plot view, the drawing will look more and more like a black tour as the computation continues.

When the solution process is complete, the optimal tour is drawn in the Plot view.

Geometric Duality: Plot view

When Geometric Duality is the selected algorithm, the Plot view displays the drawing of control zones and moats after the algorithm has terminated. Please try this with a small number of cities, say 35 or so, to get an understanding of the lower bound provided by linear programming.

TSP Art: Plot view

When TSP Art is the selected algorithm, the Plot view will initially display a set of points that will be used as cities in a TSP. In Grid mode, the points should appear quickly after loading an image. In Swarm or Lloyd's mode, the point-generation process will take a minute or two, and a % completion indicator is displayed at the bottom of the screen.

Once the points appear, the app will compute a tour to render the loaded image. The tour will be displayed after the Chained Lin-Kernighan heuristic completes the computation. It is not typically an optimal tour for the point set, but it should give an interesting rendering of the original image.

The drawing algorithm works best with portraits or with images having large identifiable structures.


Log view

Exact Solver: Log view

When the run of the Chained Lin-Kernighan heuristic is complete, the Log view will indicate the length of the best tour that is found.

During the cutting-plane process, the Log view displays messages of the form "Found k ___ cuts", indicating that the code has found k violated inequalities of the type ___ that can be used as cutting planes. After a round of cutting planes, a message "LP Value x: y", where x is the number of the round and y is the optimal value of the current LP relaxation is displayed and the plot view is updated. Lines "New lower bound: z" indicate that the LP has taken into consideration all possible edges, thus z is a lower bound on the length of any tour. After such a line, the counter x is reset to 1.

When the branch-and-bound search is running, the Log view will display lines "BBr, Depth s: t", where r is the number of the subproblem, s is the depth in the search tree, and t is the LP value for the subproblem. The word "PRUNE" indicates that the LP value is greater than the length of a known tour, and thus the subproblem can be eliminated.

When the solution process is complete, the optimal tour order will be displayed. The cities are labeled from 0 up to n-1 in the display.

Geometric Duality: Log view

When Geometric Duality is the selected algorithm, the Log view displays the length of the tour found by the Chained Lin-Kernighan heuristic, the value of the lower bound obtained with control zones and moats, and the percentage gap between the length of the tour and the value of the bound.

TSP Art: Log view

When TSP Art is the selected algorithm, the Log view displays the number of points in the generated TSP instance and the length of the tour found by Chained Lin-Kernighan.


TSPLIB format

Professor Gerhard Reinelt of the University of Heidelberg created the TSPLIB format to provide a standard means for TSP researchers to exchange test data. Full documentation can be found on his TSPLIB Web page.

The format can express either geometric instances, with (x,y) coordinates for each city, or instances with explicit distance matrices. The following two examples show you how to create these two types of files.

Example 1: Geometric data

Here is an example of a TSPLIB file for a 10-city problem defined by (x,y) coordinates.
NAME: sample10
TYPE: TSP
COMMENT: 10-city geometric problem
DIMENSION: 10
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 64 96
2 80 39
3 69 23
4 72 42
5 48 67
6 58 43
7 81 34
8 79 17
9 30 23
10 42 67
EOF
The line
DIMENSION: 10
indicates that there are 10 cities in the problem, and the line
EDGE_WEIGHT_TYPE: EUC_2D
indicates that the travel costs are given by the Euclidean distances, that is, the straight-line distance, between each pair of points.

The first point is (64, 96), the second point is (80, 39), and so on.

The final line reads "EOF", indicating it is the end of file.

Example 2: explicit distances

Here is an example of a TSPLIB file for a 10-city problem defined by an explicit matrix of travel distances.
NAME: matrix10
TYPE: TSP
COMMENT: 10-city explicit problem
DIMENSION: 10
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
 0
 63 0
 25 39 0
 19 66 22 0
 41 22 16 38 0
 15 48 11 12 26 0
 80 57 19 77 35 63 0
 13 53 15 10 30 34 29 0
 25 55 37 17 33 26 23 24 0
 50 28 26 47 19 36 44 40 49 0
EOF

The line

EDGE_WEIGHT_TYPE: EXPLICIT
indicates that explicit travel costs are given for each pair of cities and the line
EDGE_WEIGHT_FORMAT
indicates that these costs are given as a lower-diagonal matrix.

The travel costs from each city to itself is set to 0; these are the 0 values at the end of each data line.

For city 2, the travel cost to city 1 is 63. For city 3, the travel cost to city 1 is 25 and the cost to city 2 is 39. And so on.