Local search for traveling salesman and constraint problems often takes exponential time

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment

Data Structures and Algorithms

Summary

This paper shows that for some important optimization problems, local search methods can take an extremely long time—exponential in length—before reaching the best solution they can find. The authors prove this for the traveling salesman problem using a common neighborhood technique called 2-opt, and for some complex constraint assignment problems. This completes a picture researchers had been building for years by proving that even the simplest local improvements can lead to very long solution paths. Their work also shows a surprising connection between seemingly different problems, revealing underlying complexity in how local search explores solutions.

What this means in practice

A theory result. No direct application yet.

Authors

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

Abstract

We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every $k$-opt neighborhood with $k \ge 3$, so our result for $2$-opt completes the picture for all $k$-kopt neighborhoods. In $(p,q,r)$-Maximum Constraint Assignment, each constraint involves at most $p$ variables, each variable occurs in at most $q$ constraints, and each domain has size $r$. Decreasing any of the parameters of $(3,2,2)$ or $(2,3,2)$ yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.
View PDFOpen arXiv