Question

Offer one example of an IT or computer application that can be modeled as the TSP problem. This must be at least one paragraph. (something other than scheduling a bunch of jobs on a single machine)

Answer 1

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed.

the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases super polynomially (but no more than exponentially) with the number of cities.

The traditional lines of attack for the NP-hard problems are the following:

• Devising exact algorithms, which work reasonably fast only for small problem sizes.
• Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver approximated solutions in a reasonable time.
• Finding special cases for the problem ("sub problems") for which either better or exact heuristics are possible.

Exact algorithms

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute-force search). The running time for this approach lies within a polynomial factor of {O(n!)}, the factorial of the number of cities, so this solution becomes impractical even for only 20 cities.

One of the earliest applications of dynamic programming is the Held–Karp algorithm that solves the problem in time { O(n^{2}*2^{n})}.This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.

• Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 200 cities.
• Implementations of branch-and-bound and problem-specific cut generation (branch-and-cut); this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities.