What software is there for the Traveling Salesman Problem?
This famously hard problem — known more briefly as the TSP — is to find the shortest tour that visits a given collection of cities or locations of some kind. It is a hard (NP-complete) problem just like [#Q3 integer programming], but the obvious integer programming formulations of it are not especially useful in getting good solutions within a reasonable amount of time. The TSP has attracted many of the best minds in the optimization field, and serves as a kind of test-bed for methods subsequently applied to more complex and practical problems. Methods have been explored both to give proved optimal solutions, and to give approximate but “good” solutions, with a number of codes being developed as a result: • Concorde has solved a number of the largest TSPs for which proved optimal solutions are known. It employs a polyhedral approach, which is to say that it relies on a range of exceedingly sophisticated linear programming constraints, in a framework that resembles integer programming
