Concorde: 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.

The Concorde TSP Solver package is freely available for academic research and has to be obtained separately from the Concorde web site (see details).

Usage

## set path for executables
concorde_path(path)
## obtain a list of command line options for the solvers
concorde_help()
linkern_help()

Arguments

path

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

Details

The code of the Concorde TSP package is not included in this package and has to be obtained separately from the Concorde web site (see references). Either download the precompiled executables and place them in a suitable directory and make them executable, or you can get the source code and compile it 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 link{Sys.setenv}).

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.

References

Concorde home page, http://www.tsp.gatech.edu/concorde/

Concorde download page, http://www.tsp.gatech.edu/concorde/downloads/downloads.htm

David Appletgate, 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.

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

Examples

Run this code

## 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 only with fast cuts (-V)
# solve_TSP(USCA312, method = "concorde", control = list(clo = "-V"))
# ## End(Not run)