The Concorde TSP Solver is a program for solving the
travelling salesman problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
. It was written by
David Applegate
David L. Applegate is an American computer scientist known for his research on the traveling salesperson problem.
Education
Applegate graduated from the University of Dayton in 1984, and completed his doctorate in 1991 from Carnegie Mellon U ...
,
Robert E. Bixby,
Vašek Chvátal, and
William J. Cook, in
ANSI C
ANSI C, ISO C, and Standard C are successive standards for the C programming language published by the American National Standards Institute (ANSI) and ISO/IEC JTC 1/SC 22/WG 14 of the International Organization for Standardization (ISO) and the ...
, and is freely available for academic use.
Concorde has been applied to problems of
gene mapping
Gene mapping or genome mapping describes the methods used to identify the location of a gene on a chromosome and the distances between genes. Gene mapping can also describe the distances between different sites within a gene.
The essence of all ...
,
protein function prediction,
vehicle routing
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises ...
, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.
According to , Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000
guilder
Guilder is the English translation of the Dutch and German ''gulden'', originally shortened from Middle High German ''guldin pfenninc'' (" gold penny"). This was the term that became current in the southern and western parts of the Holy Rom ...
prize from
CMG for solving a vehicle routing problem the company had posed in 1996.
Concorde requires a
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
solver and only supports QSopt
and
CPLEX
IBM ILOG CPLEX Optimization Studio (often informally referred to simply as CPLEX) is an optimization software package.
History
The CPLEX Optimizer was named after the simplex method implemented in the C programming language. However, today ...
8.0.
Notes
References
*.
*.
*.
*.
*.
*.
*.
{{refend
External links
Concorde website
at Arizona State University
Arizona State University (Arizona State or ASU) is a public university, public research university in Tempe, Arizona, United States. Founded in 1885 as Territorial Normal School by the 13th Arizona Territorial Legislature, the university is o ...
Travelling salesman problem
Mathematical optimization software