bonndata catalog
Thumbnail for Hard to Solve Instances of the Euclidean Traveling Salesman Problem

Hard to Solve Instances of the Euclidean Traveling Salesman Problem

Open this dataset in the live repository

Important usage condition: Use and redistribution are governed by CC BY 4.0. Review and comply with the license before using the data.
Persistent identifier
doi:10.60507/FK2/ESZ1QZ
Published version
1.0
Publication date
2024-05-24
License
CC BY 4.0

Description

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. 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. Finally we make all the .log-files available of the runs of Concorde we describe in our paper.

Creators

Keywords

Traveling Salesman Problem

Files

Before downloading: Use and redistribution are governed by CC BY 4.0. Review and comply with the license before using the data.
FileTypeBytesChecksum
Tnm_instances.zipapplication/zip50926MD5 943f09dd8af1f1fdef657f3fd908b75f
Tnm.cpptext/plain2716MD5 7b508033774a937159bf8c85eae0d73e
TSPLIB_logfiles.zipapplication/zip33528446MD5 6a0a7cec5b11f92d8d55f1d3b0e0b38b
Tnm_logfiles.zipapplication/zip183412376MD5 039307e746f02f7901bd49be087af1a2
readme.txttext/plain1398MD5 3dc19eb685e8320cb971646a564b93b3

Citation

Hougardy, Stefan, 2024-05-24, Hard to Solve Instances of the Euclidean Traveling Salesman Problem, doi:10.60507/FK2/ESZ1QZ, V1.0

Additional Dataverse fields

Id226
Dataset Typedataset
Internal Version Number12
Latest Version Publishing StateRELEASED
Deaccession LinkNot supplied
Release Time2024-05-24T07:53:29Z
Create Time2024-05-21T12:16:07Z
Citation Date2024-05-24
File Access RequestTrue

Export metadata

Static metadata exports available for this published dataset version:

Complete Dataverse metadata

Citation Metadata

Title title
Hard to Solve Instances of the Euclidean Traveling Salesman Problem
Alternative URL alternativeURL
http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html
Author author
  1. Author Name
    Hougardy, Stefan
    Author Affiliation
    University of Bonn
    Author Identifier Scheme
    ORCID
    Author Identifier
    Type Name
    authorIdentifier
    Multiple
    False
    Type Class
    primitive
    Value
    https://orcid.org/0000-0001-8656-3418
    Expandedvalue
    Person Name
    Hougardy, Stefan
    @id
    https://orcid.org/0000-0001-8656-3418
    Scheme
    ORCID
    @type
    https://schema.org/Person
Dataset Contact datasetContact
  1. Dataset Contact Name
    Hougardy, Stefan
    Dataset Contact Affiliation
    University of Bonn
    Dataset Contact Email
    shougard@uni-bonn.de
Ds Description dsDescription
  1. Ds Description Value
    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. 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. Finally we make all the .log-files available of the runs of Concorde we describe in our paper.
    Ds Description Date
    2024-05-21
Subject subject
  1. Computer and Information Science
  2. Mathematical Sciences
Free Keyword freeKeyword
  1. Free Keyword Value
    Traveling Salesman Problem
Publication publication
  1. Publication Citation
    Hougardy, S., Zhong, X. Hard to solve instances of the Euclidean Traveling Salesman Problem. Math. Prog. Comp. 13, 51–74 (2021). https://doi.org/10.1007/s12532-020-00184-5
    Publication IDType
    doi
    Publication IDNumber
    10.1007/s12532-020-00184-5
    Publication URL
    https://doi.org/10.1007/s12532-020-00184-5
Depositor depositor
Hougardy, Stefan
Date Of Deposit dateOfDeposit
2024-05-21

Expected crawler behaviour

Use a stable, truthful User-Agent with product/version and a working contact URL. Across all IP addresses and HTTP connections used by one crawler identity, allow no more than 5 requests in flight and wait at least 20 seconds between request starts. Crawl URLs listed in the catalog sitemap, including file pages and download URLs when they are published, use conditional requests, honor Retry-After, and apply exponential backoff after errors.

The welcome page may link to the interactive repository for human navigation. Automated clients must not treat that human link as a catalog crawl target.

Read the live machine-readable crawler policy before and during a crawl. Stop crawling when it reports CPU or memory utilization at or above 80% and 80% respectively.