The basic principle using the branchand- bound strategy to solve the traveling salesperson optimization problem (TSP) consists of two parts. There is a way to split the solution space. There is a way to predict a lower bound for a class of solutions. There is also a way to find an upper bound of an optimal solution. If the lower bound of a solution exceeds this upper bound, this solution cannot be optimal. Thus, we should terminate the branching associated with this solution.
