Concorde TSP Solver
{{Short description|Program for solving the travelling salesman problem}}
{{Infobox software
| title = Concorde
| author = David Applegate, Robert Bixby, Václav Chvátal, William J. Cook
| released = {{Start date and age|1997|8|27}}
| discontinued =
| latest release version = 03.12.19
| latest release date = {{Start date and age|2003|12|19}}
| repo = {{URL|https://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm}}
| programming language = C
| operating system = Linux, Oracle Solaris, Microsoft Windows (with Cygwin)
| size = 1.3 MB
| language = English
| genre = Mathematical optimization software
| license = Source-available, free for academic research
| website = {{URL|https://www.math.uwaterloo.ca/tsp/concorde.html}}
}}
The Concorde TSP Solver is a program for solving the travelling salesman problem. It was written by David Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook, in ANSI C, and is freely available for academic use.
Concorde has been applied to problems of gene mapping,{{harvtxt|Hitte|Lorentzen|Guyon|Kim|2003}}. protein function prediction,{{harvtxt|Johnson|Liu|2006}}. vehicle routing,{{harvtxt|Applegate|Cook|Dash|Rohe|2002}}. conversion of bitmap images to continuous line drawings,{{harvtxt|Bosch|Herman|2004}}. scheduling ship movements for seismic surveys,{{harvtxt|Gutin|Jakubowicz|Ronen|Zverovitch|2005}} and in studying the scaling properties of combinatorial optimization problems.{{harvtxt|Aldous|Percus|2003}}.
According to {{harvtxt|Mulder|Wunsch|2003}}, Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000 guilder prize from CMG for solving a vehicle routing problem the company had posed in 1996.[http://www.tsp.gatech.edu/apps/whizzkids.html Whizzkids '96 vehicle routing], from the Concorde web site, retrieved August 26, 2008.
Concorde requires a linear programming solver and only supports QSopt{{cite web |title=QSopt Linear Programming Solver |url=https://www.math.uwaterloo.ca/~bico/qsopt/ |publisher=University of Waterloo |access-date=28 October 2023}} and CPLEX 8.0.
Notes
{{Reflist}}
References
{{refbegin|2}}
- {{citation
| last1 = Aldous | first1 = David
| last2 = Percus | first2 = Allon G.
| doi = 10.1073/pnas.1635191100
| issue = 20
| journal = Proc. Natl. Acad. Sci. USA
| pages = 11211–11215
| title = Scaling and universality in continuous length combinatorial optimization
| volume = 100
| year = 2003
| pmid = 14504403
| pmc = 208736| bibcode = 2003PNAS..10011211A
| arxiv = cond-mat/0301035| doi-access = free
}}.
- {{citation
| last1 = Applegate | first1 = David
| last2 = Cook | first2 = William
| last3 = Dash | first3 = Sanjeeb
| last4 = Rohe | first4 = André
| doi = 10.1287/ijoc.14.2.132.118
| issue = 2
| journal = INFORMS Journal on Computing
| pages = 132–143
| title = Solution of a min-max vehicle routing problem
| volume = 14
| year = 2002}}.
- {{citation
| last1 = Bosch | first1 = Robert
| last2 = Herman | first2 = Adrianne
| doi = 10.1016/j.orl.2003.10.001
| issue = 4
| journal = Operations Research Letters
| pages = 302–303
| title = Continuous line drawings via the traveling salesman problem
| url = http://www.oberlin.edu/math/faculty/bosch/cld.pdf
| volume = 32
| year = 2004}}.
- {{citation
| last1 = Gutin | first1 = Gregory
| last2 = Jakubowicz | first2 = Helmut
| last3 = Ronen | first3 = Shuki
| last4 = Zverovitch | first4 = Alexei
| journal = Communications in DQM
| pages = 13–20
| title = Seismic vessel problem
| url = http://www.cs.rhul.ac.uk/home/gutin/paperstsp/svp5.pdf
| volume = 8
| year = 2005}}.
- {{citation
| last1 = Hitte | first1 = C.
| last2 = Lorentzen | first2 = T. D.
| last3 = Guyon | first3 = R.
| last4 = Kim | first4 = L.
| last5 = Cadieu | first5 = E.
| last6 = Parker | first6 = H. G.
| last7 = Quignon | first7 = P.
| last8 = Lowe | first8 = J. K.
| last9 = Gelfenbeyn | first9 = B.
| last10 = Andre
| first10 = C
| last11 = Ostrander
| first11 = E. A.
| last12 = Galibert
| first12 = F
| doi = 10.1093/jhered/esg012
| issue = 1
| journal = Journal of Heredity
| pages = 9–13
| title = Comparison of MultiMap and TSP/CONCORDE for constructing radiation hybrid maps
| volume = 94
| year = 2003
| pmid = 12692156| display-authors = 8
| doi-access = free
}}.
- {{citation
| last1 = Johnson | first1 = Olin
| last2 = Liu | first2 = Jing
| doi = 10.1186/1751-0473-1-3
| journal = Source Code for Biology and Medicine
| page = 3
| title = A traveling salesman approach for predicting protein functions
| volume = 1
| year = 2006
| pmid = 17147783
| pmc = 1636333
| doi-access = free
}}.
- {{citation
| last1 = Mulder | first1 = Samuel A.
| last2 = Wunsch | first2 = Donald C., II
| doi = 10.1016/S0893-6080(03)00130-8
| issue = 5–6
| journal = Neural Networks
| pages = 827–832
| title = Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks
| volume = 16
| year = 2003
| pmid = 12850040}}.
{{refend}}
External links
- [http://www.math.uwaterloo.ca/tsp/concorde/ Concorde website]
- [https://neos-server.org/neos/solvers/co:concorde/TSP.html Online access to Concorde solver] at Arizona State University