A library for parsing TSPLIB files and solving instances of the traveling salesman problem
- googletest (1.6.0)
The Makefile expects to find the googletest sources in /usr/src/gtest, but an alternate location can be specified with the GTEST_DIR environment variable. Debian-based systems can install googletest to the default location by running the command sudo apt-get install libgtest-dev.
Clone this modified version of the Concorde source code to a directory on your system. The Makefile expects to find the Concorde sources in /usr/local/src/concorde, but an alternate location can be specified with the CONCORDE_DIR environment variable.
Download the static library (qsopt.a) and header file (qsopt.h) from the QSopt website and place them in a directory on your system. The Makefile expects to find these files in /usr/local/lib/qsopt, but an alternate location can be specified with the QSOPT_DIR environment variable.
Use sudo apt-get install libcairomm-1.0-dev to get and install Cairomm and its dependencies on your system. The Makefile will use the pkg-config utility to find and include the necessary files.
- Open MPI (1.6.5)
Use sudo apt-get install openmpi-bin openmpi-doc libopenmpi-dev to get and install Open MPI and its dependecies on your system.
make
will build all distributed executables.
make tests
will build all test executables.
make test
will build any outdated test executables and run all unit tests.
parse_tsp attempts to read in a TSPLIB formatted file. After reading in a properly formatted TSPLIB file, parse_tsp will output the information it has properly parsed from the file.
./parse_tsp <tsp_file>
solve_tsp attemps to solve an instance of the traveling salesman problem as specified by an input TSPLIB file. The algorithm with which solve_tsp solves the instance needs to be specified by the user. Also, the user must specify whether or not distances will be rounded to the nearest integer when a TSPLIB file requires edge weights to be calculated with functions (e.g. EUC_2D, GEO, etc.). All files that are part of the default TSPLIB distribution require nearest int rounding to compute their published optimal solutions. A 1 indicates that nearest int rounding should be used and a 0 indicates that double floating point precision should be used.
./solve_tsp <tsp_file> <algorithm> <nearest_int>
A list of supported algorithms can be displayed by running the program with -algorithms as the only parameter.
./solve_tsp -algorithms
generate_tsp randomly generates a TSP instance and exports the instance to a TSPLIB formatted file. Minimum and maximum values for the cities' coordinates must be specified with the min_coord and max_coord parameters.
./generate_tsp <tsp_name> <number_of_cities> <min_coord> <max_coord> <output_file>
single_city_simulation runs a specified number of simulations where the optimal path for a randomly generated TSP instance is computed, a city in the instance is deleted uniformly at random, and a new city is added with new coordinates generated uniformly at random. Minimum and maximum values for the cities' coordinates must be specified with the min_coord and max_coord parameters. input_file specifies the TSPLIB-formatted file that defines the input TSP instance and output_dir specifies the output directory. The max_chunk_size parameter is used by the Concorde Solver; to learn more about how this value affects the solution finding process, see the Concorde documentation.
./bin/single_city_simulation <output_dir> <iterations> <min_coord> <max_coord> <input_file> <max_compute_time> <max_chunk_size>
two_city_simulation runs a specified number of simulations where the optimal path for a randomly generated TSP instance is first computed. Then a city in the instance is replaced uniformly at random, a new city is added with new coordinates generated uniformly at random, and the optimal path is recomputed. This procedure is repeated for a different city. Finally, both of the cities are replaced with their respective replacements and the optimal path is computed.
./bin/two_city_simulation <output_dir> <iterations> <min_coord> <max_coord> <trials_start> <trials_end> <input_file> <max_compute_time> <max_chunk_size> <processors> <concorde_exec> <mpi_wrapper_exec> <hostfile> [approx]
output_dir: the output directory for simulation dataiterations: the number of simulations to run. Note the difference between iterations and trials: each iteration runs (trials_end-trials_start) trials of the above procedure.min_coord: the minimum possible value that the x and y coordinates of randomly generated cities can takemax_coord: the maximum possible value that the x and y coordinates of randomly generated cities can taketrials_start: the trial number at which to start each iteration of the simulationtrials_end: the trial number at which to end each iteration of the simulationinput_file: the TSPLIB-formatted file which specifies the input TSP instancemax_compute_time: currently unused parameter; will not affect the simulation processmax_chunk_size: used by the Concorde Solver; to learn more about how this value affects the solution finding process, see the Concorde documentation.processors: the number of processors to use per trialconcorde_exec: the file location of the Concorde Solver executablempi_wrapper_exec: the location of the MPI Wrapper Executable; this file is included in this library and is made to thebindirectory. It is used to run non-MPI programs in an MPI environment.hostfile: the location of the file which specifies the addresses of the available hosts in the MPI environment.approx: specifies whether the TSP cycle lengths will be calculated approximately or exactlyseed: an optional parameter specifying the random number generator seed. If not provided, a seed will be chosen based on the system time.
Note that the mpi_wrapper_exec and hostfile arguments only apply when processors is a number greater than 1. Otherwise, the
simulation will run on a single core and will not use these extra parameters.