# Prize-Collecting Traveling Salesman Problem on PCTSP Average across scales 20, 50, 100

Source: [Prize-Collecting Traveling Salesman Problem on PCTSP Average across scales 20, 50, 100](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesman-problem-on-pctsp-average-across-scales-20-50-100>)

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

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

Evaluation of algorithms solving the Prize-Collecting Traveling Salesman Problem (PCTSP) averaged across instance sets of scales N=20, N=50, and N=100, reporting the Average 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 Salesman Problem |
| Dataset (including any stated split) | PCTSP Average across scales 20, 50, 100 |
| Metric | Average Optimality Gap |
| Unit | PERCENT |
| Direction | Lower is better |
| Results loaded | 11 of 11 |
| 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

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

## Recorded results

| Method | Average Optimality Gap | Result date | Report paper |
| --- | --- | --- | --- |
| ILS | 0.36 | Not recorded | 68fa7ab11e209131cea84a7a |
| OR-Tools | 5.77 | Not recorded | 68fa7ab11e209131cea84a7a |
| DIFU-Ada | 9.7 | Not recorded | 68fa7ab11e209131cea84a7a |
| ASP | 11.32 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM | 13.11 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM-FT | 13.44 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM-FT | 15.92 | Not recorded | 68fa7ab11e209131cea84a7a |
| AM | 16.65 | Not recorded | 68fa7ab11e209131cea84a7a |
| MDAM | 16.93 | Not recorded | 68fa7ab11e209131cea84a7a |
| MDAM | 22.19 | Not recorded | 68fa7ab11e209131cea84a7a |
| ILS (Python 10x) | 140.35 | Not recorded | 68fa7ab11e209131cea84a7a |

### ILS

Average Optimality Gap: 0.36. Result ID: 69b273916dbb7075b95ce3b5.

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

Recorded evaluation configuration: {"Implementation Language":"C++"}. This record does not assert independent reproduction.

### OR-Tools

Average Optimality Gap: 5.77. Result ID: 69b273916dbb7075b95ce3b4.

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

Recorded evaluation configuration: {"Training-free":"—"}. This record does not assert independent reproduction.

### DIFU-Ada

Average Optimality Gap: 9.7. Result ID: 69b273916dbb7075b95ce3be.

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

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

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

### ASP

Average Optimality Gap: 11.32. Result ID: 69b273916dbb7075b95ce3bb.

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

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

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

### AM

Average Optimality Gap: 13.11. Result ID: 69b273916dbb7075b95ce3b8.

[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: {"Search Strategy":"Sampling","Training-free":"false","Training Time":"3.5 days"}. This record does not assert independent reproduction.

### AM-FT

Average Optimality Gap: 13.44. Result ID: 69b273916dbb7075b95ce3bd.

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

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

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

### AM-FT

Average Optimality Gap: 15.92. Result ID: 69b273916dbb7075b95ce3bc.

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

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

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

### AM

Average Optimality Gap: 16.65. Result ID: 69b273916dbb7075b95ce3b7.

[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: {"Search Strategy":"Greedy","Training-free":"false","Training Time":"3.5 days"}. This record does not assert independent reproduction.

### MDAM

Average Optimality Gap: 16.93. Result ID: 69b273916dbb7075b95ce3ba.

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

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

Recorded evaluation configuration: {"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

Average Optimality Gap: 22.19. Result ID: 69b273916dbb7075b95ce3b9.

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

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

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

### ILS (Python 10x)

Average Optimality Gap: 140.35. Result ID: 69b273916dbb7075b95ce3b6.

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

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

Recorded evaluation configuration: {"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.
