Weiqi Li

By Weiqi Li

The traveling salesman problem (TSP) is presumably difficult to solve exactly using local search algorithms. It can be exactly solved by only one algorithm—the enumerative search algorithm. However, the scanning of all possible solutions requires exponential computing time. Do we need exploring all the possibilities to find the optimal solution? How can we narrow down the search space effectively and efficiently for an exhausted search? This chapter attempts to answer these questions. A local search algorithm is a discrete dynamical system, in which a search trajectory searches a part of the solution space and stops at a locally optimal point. A solution attractor of a local search system for the TSP is defined as a subset of the solution space that contains all locally optimal tours. The solution attractor concept gives us great insight into the computational complexity of the TSP. If we know where the solution attractor is located in the solution space, we simply completely search the solution attractor, rather than the entire solution space, to find the globally optimal tour. This chapter describes the solution attractor of local search system for the TSP and then presents a novel search system—the attractor-based search system—that can solve the TSP much efficiently with global optimality guarantee.

Part of the book: Novel Trends in the Traveling Salesman Problem

By Weiqi Li

The Traveling Salesman Problem (TSP) is believed to be an intractable problem and have no practically efficient algorithm to solve it. The intrinsic difficulty of the TSP is associated with the combinatorial explosion of potential solutions in the solution space. When a TSP instance is large, the number of possible solutions in the solution space is so large as to forbid an exhaustive search for the optimal solutions. The seemingly “limitless” increase of computational power will not resolve its genuine intractability. Do we need to explore all the possibilities in the solution space to find the optimal solutions? This chapter offers a novel perspective trying to overcome the combinatorial complexity of the TSP. When we design an algorithm to solve an optimization problem, we usually ask the critical question: “How can we find all exact optimal solutions and how do we know that they are optimal in the solution space?” This chapter introduces the Attractor-Based Search System (ABSS) that is specifically designed for the TSP. This chapter explains how the ABSS answer this critical question. The computing complexity of the ABSS is also discussed.

Part of the book: Theory of Complexity