Data · dataset · 2024
Hard to Solve Instances of the Euclidean Traveling Salesman Problem
Listed in bonndata
In our paper Hard to Solve Instances of the Euclidean Traveling Salesman Problem (Mathematical Programming Computation (2021) 13:51-74) we construct a family of Euclidean instances for the Traveling Salesman Problem for which the integrality ratio of the subtour LP converges to 4/3.
Description
These instances turn out to be very hard to solve with exact TSP solvers. On a 200 vertex instance from our family, Concorde, the fastest known exact TSP solver, needs more than 1,000,000 times the runtime it needs for TSPLIB instances of similar size.
On a 1000 vertex instance the runtime factor is already about 10^27. Here we provide instances with up to 200 vertices from our family in TSPLIB format. We also provide code for generating these instances for an arbitrary number of vertices.
Read the rest (1 more)
Finally we make all the .log-files available of the runs of Concorde we describe in our paper.
Links
Where it is published
- Dataverse dataset page bonndata.uni-bonn.de/dataset.xhtml?persistentId=doi%3A10.60507%2FFK2%2FESZ1QZ ↗
landing page · from bonndata uni bonn de
- DOI doi.org/10.60507/fk2/esz1qz ↗
DOI / persistent id · from bonndata uni bonn de
Catalogue records · 1
- Dataverse API bonndata.uni-bonn.de/api/datasets/:persistentId/?persistentId=doi%3A10.60507%2FFK2%… ↗
metadata API · from bonndata uni bonn de
Topics
- Stated by source
- Computer and Information Science · Mathematical Sciences
- From keywords
- Mathematics & Statistics
- Inferred from text
- Combinatorics and discrete mathematics 76%
Provenance · 1 source records, 10 field assertions
| Source | Key | Last seen | Raw |
|---|---|---|---|
| bonndata | doi:10.60507/FK2/ESZ1QZ | 11 d ago | JSON v1 |
| Field | Assertion | Extractor | Evidence |
|---|---|---|---|
| concepts[field].anzsrc:field:490404 | enrichment · bonndata uni bonn de | taxonomy-embedding@1.1.0 | title+keywords+description (76%) |
| concepts[field].dataverse_subject:computer-and-information-science | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | /subjects |
| concepts[field].dataverse_subject:mathematical-sciences | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | /subjects |
| concepts[field].local:field:mathematics-statistics | mapping · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | /subjects |
| created_date | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | |
| description | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | /description |
| publication_date | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | |
| title | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | /name |
| updated_date | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 | |
| version_label | source · bonndata uni bonn de | connector:bonndata_uni_bonn_de@1.0.0 |