# Prize-Collecting Traveling Salesperson Problem on PCTSP-20

Source: [Prize-Collecting Traveling Salesperson Problem on PCTSP-20](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-20>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-03-12T08:04:56.735Z

Evaluation of algorithms solving the Prize-Collecting Traveling Salesperson Problem (PCTSP) specifically on the PCTSP-20 instance set, reporting solution cost and optimality gap.

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

| Scope | Recorded value |
| --- | --- |
| Task | Prize-Collecting Traveling Salesperson Problem |
| Dataset (including any stated split) | PCTSP-20 |
| Metric | Optimality Gap |
| Unit | PERCENT |
| Direction | Lower is better |
| Results loaded | 15 of 15 |
| Coverage | All results currently returned for this benchmark |

Evaluation settings may differ between results. The original papers and recorded configurations are needed to establish comparability. A shared metric name alone does not establish an identical protocol.

## Metrics

- [Optimality Gap](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-20.md?metric=Optimality%20Gap>): Lower is better; unit: PERCENT.

- [Solution Cost](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-20.md?metric=Solution%20Cost>): Lower is better; unit: SCALAR.

## Recorded results

| Method | Optimality Gap | Result date | Report paper |
| --- | --- | --- | --- |
| Gurobi | 0 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM-FT | 1.02 | Not recorded | 68fa7ab11e209131cea84a7a |
| ILS | 1.07 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM-FT | 2.11 | Not recorded | 68fa7ab11e209131cea84a7a |
| OR-Tools | 2.13 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM | 2.54 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM | 2.76 | Not recorded | 68fa7ab11e209131cea84a7a |
| DIFU-Ada | 4.2 | Not recorded | 68fa7ab11e209131cea84a7a |
| DIFU-Ada | 4.45 | Not recorded | 68fa7ab11e209131cea84a7a |
| MDAM | 5.88 | Not recorded | 68fa7ab11e209131cea84a7a |
| MDAM | 11.76 | Not recorded | 68fa7ab11e209131cea84a7a |
| ASP | 12.05 | Not recorded | 68fa7ab11e209131cea84a7a |
| T2T | 14.82 | Not recorded | 68fa7ab11e209131cea84a7a |
| DIFUSCO | 19.21 | Not recorded | 68fa7ab11e209131cea84a7a |
| ILS (Python 10x) | 63.23 | Not recorded | 68fa7ab11e209131cea84a7a |

### Gurobi

Optimality Gap: 0. Result ID: 69b273916dbb7075b95ce392.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Inference Time":"3.10s"}. This record does not assert independent reproduction.

### AM-FT

Optimality Gap: 1.02. Result ID: 69b273916dbb7075b95ce39c.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa73a81e209131cea5dbbd.md>)

Recorded evaluation configuration: {"Inference Time":"2.51s","Search Strategy":"Sampling","Training-free":"false","Training Time":"4.9 days"}. This record does not assert independent reproduction.

### ILS

Optimality Gap: 1.07. Result ID: 69b273916dbb7075b95ce394.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Inference Time":"2.13s","Implementation Language":"C++"}. This record does not assert independent reproduction.

### AM-FT

Optimality Gap: 2.11. Result ID: 69b273916dbb7075b95ce39b.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa73a81e209131cea5dbbd.md>)

Recorded evaluation configuration: {"Inference Time":"0.03s","Search Strategy":"greedy","Training-free":"false","Training Time":"4.9 days"}. This record does not assert independent reproduction.

### OR-Tools

Optimality Gap: 2.13. Result ID: 69b273916dbb7075b95ce393.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Inference Time":"12.31s"}. This record does not assert independent reproduction.

### AM

Optimality Gap: 2.54. Result ID: 69b273916dbb7075b95ce397.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa75bc1e209131cea699d8.md>)

[Implementation](<https://www.sota2.com/Code%20will%20be%20available%20soon.>)

Recorded evaluation configuration: {"Inference Time":"2.43s","Search Strategy":"Sampling","Training-free":"false","Training Time":"3.5 days"}. This record does not assert independent reproduction.

### AM

Optimality Gap: 2.76. Result ID: 69b273916dbb7075b95ce396.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa75bc1e209131cea699d8.md>)

[Implementation](<https://www.sota2.com/Code%20will%20be%20available%20soon.>)

Recorded evaluation configuration: {"Inference Time":"0.02s","Search Strategy":"Greedy","Training-free":"false","Training Time":"3.5 days"}. This record does not assert independent reproduction.

### DIFU-Ada

Optimality Gap: 4.2. Result ID: 69b273916dbb7075b95ce385.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Zero-shot":"true","TSP-trained":"true","Decoding":"Greedy","Time":"1.72s"}. This record does not assert independent reproduction.

### DIFU-Ada

Optimality Gap: 4.45. Result ID: 69b273916dbb7075b95ce39d.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Inference Time":"1.80s","Training-free":"true","Training Time":"0 day"}. This record does not assert independent reproduction.

### MDAM

Optimality Gap: 5.88. Result ID: 69b273916dbb7075b95ce399.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5a281e209131ce9bd626.md>)

Recorded evaluation configuration: {"Inference Time":"2.70m","Search Strategy":"Beam Search","Training-free":"false","Training Time":"4.3 days","Data Source":"reported from \[11\]"}. This record does not assert independent reproduction.

### MDAM

Optimality Gap: 11.76. Result ID: 69b273916dbb7075b95ce398.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5a281e209131ce9bd626.md>)

Recorded evaluation configuration: {"Inference Time":"41.10s","Search Strategy":"Greedy","Training-free":"false","Training Time":"4.3 days","Data Source":"reported from \[11\]"}. This record does not assert independent reproduction.

### ASP

Optimality Gap: 12.05. Result ID: 69b273916dbb7075b95ce39a.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5a281e209131ce9bd626.md>)

Recorded evaluation configuration: {"Inference Time":"0.03s","Training-free":"false","Training Time":"4.6 days","Data Source":"reported from \[11\]"}. This record does not assert independent reproduction.

### T2T

Optimality Gap: 14.82. Result ID: 69b273916dbb7075b95ce384.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

Recorded evaluation configuration: {"Zero-shot":"true","TSP-trained":"true","Decoding":"Greedy","Time":"2.02s"}. This record does not assert independent reproduction.

### DIFUSCO

Optimality Gap: 19.21. Result ID: 69b273916dbb7075b95ce383.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa71551e209131cea50914.md>)

[Implementation](<https://github.com/Edward-Sun/DIFUSCO>)

Recorded evaluation configuration: {"Zero-shot":"true","TSP-trained":"true","Decoding":"Greedy","Time":"1.04s"}. This record does not assert independent reproduction.

### ILS (Python 10x)

Optimality Gap: 63.23. Result ID: 69b273916dbb7075b95ce395.

[Reporting paper](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5a281e209131ce9bd626.md>)

Recorded evaluation configuration: {"Inference Time":"3.05s","Implementation Language":"Python","Data Source":"reported from \[11\]"}. This record does not assert independent reproduction.

Page 1 of 1. This is an index page, not the full collection.
