Concorde: Using the Concorde TSP Solver

In mhahsler/TSP: Traveling Salesperson Problem (TSP)

Using the Concorde TSP Solver

Description

The Concorde TSP Solver package contains several solvers. Currently, interfaces to the Concorde solver (Applegate et al. 2001), one of the most advanced and fastest TSP solvers using branch-and-cut, and the Chained Lin-Kernighan (Applegate et al. 2003) implementation are provided in TSP. Concorde can solve TSPs and ETSPs directly. ATSPs are reformulated as larger TSP's and then solved.

Usage

concorde_path(path)

concorde_help()

linkern_help()

Arguments

path	a character string with the path to the directory where the executables are installed.

Details

Installation of Concorde

The Concorde TSP Solver is freely available for academic research. It is not included in the TSP R package and has to be obtained separately from the Concorde download page. Either download the precompiled executables and place them in a suitable directory (make sure they are executable), or you can get the source code and compile the program on your own. TSP needs to know where the executables are. There are two options:

1. use concorde_path() to set the path to the directory containing the executables for concorde and linkern, or

2. make sure that the executables are in the search path stored in the PATH environment variable (see Sys.setenv()).

Using Concorde for solve_TSP()

solve_TSP() uses write_TSPLIB() to write the TSP for Concorde and tries to find the appropriate precision value (digits after the decimal point) to convert the provided distances into the needed integer value range. The precision value can also be specified in control in solve_TSP() with method Concorde. Warning messages will alert the user if the conversion to integer values results into rounding errors that are worse then what is specified in the precision control parameter.

To get a list of all available command line options which can be used via the clo option for solve_TSP use concorde_help() and linkern_help(). Several options (-x, -o, -N, -Q) are not available via solve_TSP() since they are used by the interface.

If Concorde takes too long, then you can kill the 'concorde' process via your operating system and you can continue with R.

Value

Nothing.

Author(s)

Michael Hahsler

References

Concorde home page, http://www.math.uwaterloo.ca/tsp/concorde/

David Applegate, Robert Bixby, Vasek Chvatal, William Cook (2001): TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), Springer-Verlag.

David Applegate and William Cook and Andre Rohe (2003): Chained Lin-Kernighan for Large Traveling Salesman Problems, INFORMS Journal on Computing, 15, 82–92.

See Also

Other TSP: ATSP(), ETSP(), TSP(), TSPLIB, insert_dummy(), reformulate_ATSP_as_TSP(), solve_TSP()

Examples

## Not run: 
## see if Concorde is correctly installed
concorde_path()


## set path to the Concorde executible if it is not in the search PATH
## Example:
## concorde_path("~/concorde/")

concorde_help()

data("USCA312")

## run concorde in verbose mode (-v) with fast cuts only (-V)
solve_TSP(USCA312, method = "concorde", control = list(clo = "-v -V"))

## End(Not run)

mhahsler/TSP documentation built on April 24, 2024, 10:05 p.m.