Issue |
EPL
Volume 113, Number 3, February 2016
|
|
---|---|---|
Article Number | 30004 | |
Number of page(s) | 6 | |
Section | General | |
DOI | https://doi.org/10.1209/0295-5075/113/30004 | |
Published online | 25 February 2016 |
Phase transitions of Traveling Salesperson problems solved with linear programming and cutting planes
Institut für Physik, Universität Oldenburg - 26111 Oldenburg, Germany
Received: 2 January 2016
Accepted: 12 February 2016
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 solvable in polynomial time, i.e., the problem is hard. However, this 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 applications but rarely studied in physics so far. We observe several transitions. To characterize these transitions, scaling assumptions from continuous phase transitions are applied.
PACS: 02.10.Ox – Combinatorics; graph theory / 89.70.Eg – Computational complexity / 64.60.-i – General studies of phase transitions
© EPLA, 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.