Held–Karp algorithm
Exact algorithms for solving the TSP

Besides Dynamic Programming, Linear programming and Branch and bound are design patterns also used for exact solutions to the TSP. Linear programming applies the cutting plane method in integer programming, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraints to gradually converge at an optimal solution. When people apply this method to find a cutting plane, they often depend on experience, so this method is seldom used as a general method.

The term branch and bound was first used in 1963 in a paper published by Little et al. on the TSP, describing a technique of combining smaller search spaces and establishing lower bounds to enlarge the practical range of application for an exact solution. The technique is useful for expanding the number of cities able to be considered computationally, but still breaks down in large-scale data sets.

It controls the searching process through applying restrictive boundaries, allowing a search for the optimal solution branch from the space state tree to find an optimal solution as quickly as possible. The pivotal component of this algorithm is the selection of the restrictive boundary. Different restrictive boundaries may form different branch-bound algorithms.
combination:two_responses, keywords:forbidden_words