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.
The module to be run by the app is selected by tapping an image on the Home page. The choices available are Exact Solver, Tours, Bounds, Edges, TSP Art, TSP Move, and Map Router. Select the one you want by tapping the image with the appropriate label. You can always return to Home by swiping from the left edge of the screen or by tapping the navigation button on the top bar.
For each of the modules, a short information page is available by taping the Info button on the bottom bar or by swiping from the right edge of the screen. The information pages contain short descriptions of the module and the cooresponding user interface. For many of the modules additional algorithm choices or settings are also available on the information page. To make selections on these pages, tap the desired entries in the tables: a check mark will appear next to the selection.
In the Tours module, you can choose from nine methods to build a TSP tour: Nearest Neighbor, Greedy, Nearest Insertion, Farthest Insertion, Christofides' Algorithm, 2-Opt, 3-Opt, Lin-Kernighan, or Chained Lin-Kernighan. In the Starting Tour for Local Search table you can select the starting point for the 2-Opt, 3-Opt, LK, and CLK heuristics. By default, on instances with 500 or fewer cities, the plot view will animate the tour growth and improvement phases; this can be turned on or off by selecting the button on the Animation line.
In the Edges module you can choose one of six types of edge sets to construct, either a Delaunay Triangulation, k-Nearest Neighbors, Quad k-Nearest Neighbors, Fractional 2-Matching Nearest Neighbors, k-Matching (Minimum Cost k-Matching), or the Union of k Chained Lin-Kernighan Tours. The value of k can be selected with the stepper buttom.
In the Bounds module you can choose one of three modes, either Moats, Zones, or Penalties.
In the TSP Art module 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.
In the Map Router module you can select the type of travel costs that will be used to create the TSP example. The choices are Geometric -- Great Circle, Walking, and Driving. For Geometric distances you can use up to 100 cities on the map, while for Walking and Driving you can have at most 10 cities.
Data sets are selected on the Load page. You can reach the page by tapping the Load button at the bottom of the screen.
Their are five ways to select a data set: Random, Tap X-Y, Library, List X-Y, and Read. Choose the method by tapping the appropriate icon on the bottom bar. Once you have selected a method, swipe from the left edge or use the top navigation button to return to the algorithm page.
Generate a random Euclidean instance by selecting the number of cities N with the slider or the -/+ stepper. The generated cities will have random integer x-y coordinates, with x ranging from 0 up to 3200 and y ranging from 0 up to 4110.
Create a problem by tapping the screen to insert up to 100 cities. The coordinates will be scaled by 1000 to give greater precision to the TSPLIB distance function.
The app comes pre-loaded with a collection of instances that have featured in the history of the TSP. Use the picker wheel to select an example from the collection.
Create a problem by entering the x-y coordinates for up to 100 cities. Each line should contain two integer or decimal numbers. The numbers can be edited using the backspace key. The coordinates will be scaled by 1000 to give greater precision to the TSPLIB distance function.
Enter the Web location (URL) of a data file in TSPLIB format (described below).
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 spirit 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.
Once a data set is selected, the solution process is started by tapping the Run button in the bottom bar. 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 bar, 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 View button in the bottom bar.
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 TSP Art Info page to select one of the other drawing algorithms (Grid, Swarm, of Lloyd's) to see an alternative rendering of the image as a tour.
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.
If Animation is turned on (and there are 500 or fewer cities in the sample problem) then the tour construction or tour improvements will be displayed; in 2-Opt, 3-Opt, and LK, the edges removed from the tour are colored red and the edges added to reconnect the tour are colored blue. Note that the solution process is slowed down considerably by enforced delays to allow the intermediate tours or partial tours to be observed. If Animation is turned off then only the final tour is displayed.
When Bounds is the selected module, 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.
The set of constructed edges will be displayed. Note that several of the construction algorithms only work with Euclidean instances (such as those produced on the Load page using Random).
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.
An optimal tour through the small point set will be displayed. The module will continue to run until the Stop button is tapped. While the module is running, any city can be selected and dragged across the screen; the selected city will be colored red. As the city is moved, the optimal tour will be updated to reflect the new city location.
The plot view supports the usual iOS zooming-by-pinch and panning motions. For large examples the redrawing will cause a delay. In particular, zooming is turned off for Geometric Duality images for instances having more than 100 cities. To return an image to its original form, double tap the screen.
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.
The Log view will indicate the length of the tour found and the running time. If Animation is turn on, then the Log view will also contain a list of the improving tour values for the local-search methods (2-Opt, 3-Opt, LK, and CLK).
When Bounds is the selected module, 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.
When TSP Art is the selected module, the Log view displays the number of points in the generated TSP instance and the length of the tour found by Chained Lin-Kernighan.
The Log view will indicate the running time used to construct the edge set.
While a selected city is moved across the screen, the Log view records the changing length of the optimal tour.
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.
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 EOFThe line
DIMENSION: 10indicates that there are 10 cities in the problem, and the line
EDGE_WEIGHT_TYPE: EUC_2Dindicates 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.
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: EXPLICITindicates that explicit travel costs are given for each pair of cities and the line
EDGE_WEIGHT_FORMATindicates 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.