EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

73. Optimizing with attractor: combinatorial complexity of the traveling salesman problem

Invited abstract in session MA-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design I , stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Weiqi Li
School of Management, University of Michigan-Flint

Abstract

Although TSP has been placed in the subject of NP-completeness, it might not be as complex as expected. Often the seed of a solution is in the problem structure that creates the complexity. The intrinsic difficulty of TSP is due to the combinatorial explosion of tours in the solution space S, which increases in (n-1)! as TSP size n increases. In TSP, a small set of n(n-1) edges make up a large set of (n-1)! tours in S. Let S’ be a subset of S, if we can exponentially reduce S to S’ using a polynomial-time local search algorithm, and S’ can be polynomially searched by an exhaustive search algorithm, there is a polynomial algorithm for TSP. A local search can reduce S to S’ quickly using the edge matrix E of TSP as a reduction mechanism, because if one edge is removed in E, (n-2)! tours are removed in S. Instead of searching for better tours in S, our effort is to remove bad edges in E. In a local search system, an attractor S’ drives search trajectories into the vicinity of a globally optimal point in S. S’ contains a small set of the most promising tours and is exponentially smaller than S, thus make an exhaustive search feasible. This new search paradigm is called optimizing with attractor. A new search algorithm consists of two search phases: local search phase quickly construct S’ in S, and exhaustive search phase examines S’ completely to find the optimal tour. TSP size can be reduced through its own data structure, thus it is a self-reducible problem.

Keywords

Status: accepted

Back to the list of papers