Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
arXiv:1512.08554 · doi:10.1209/0295-5075/113/30004
Abstract
The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means that with all known algorithms in the worst case instances are not solveable in polynomial time, i.e., the problem is hard. Though that does not mean, that there are not subsets of the problem which are easy to solve. To examine numerically transitions from an easy to a hard phase, a random ensemble of cities in the Euclidean plane given a parameter σ, which governs the hardness, is introduced. Here, a linear programming approach together with suitable cutting planes is applied. Such algorithms operate outside the space of feasible solutions and are often used in practical application but rarely studied in physics so far. We observe several transitions. To characterize these transitions, scaling assumptions from continuous phase transitions are applied
arXiv comment4 pages, 6 figures
References in corpus (7)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
- Statistical mechanics of the vertex-cover problem
- Phase transition for cutting-plane approach to vertex-cover problem
- Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
Cited by in corpus (6)
- Collective effects of the cost of opinion change
- Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
- Typical Approximation Performance for Maximum Coverage Problem
- Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
- Phase transition in the bipartite z-matching
- Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers