Metraipolis › archive › dc_4762ffd48e44

Unmasking Four Knapsack Problems in the Traveling Thief Benchmark — arXiv:2611.12597

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.12597
License (as archived)
CC0-1.0
Archived
2026-11-10T18:44:12.282Z
SHA-256 of the archived text
898e1c5f919c053bd60b7ff2c33a62f5d1c87aa89eeb5424613a5b4ff200c373
Stable URL of this page
https://metraipolis.com/documento/dc_4762ffd48e44

How to cite

Unmasking Four Knapsack Problems in the Traveling Thief Benchmark — arXiv:2611.12597 — arXiv (en), https://arxiv.org/abs/2611.12597 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4762ffd48e44 (Metraipolis archive dc_4762ffd48e44, sha256 898e1c5f919c053bd60b7ff2c33a62f5d1c87aa89eeb5424613a5b4ff200c373)
BibTeX
@misc{dc4762ffd48e44,
  title = {Unmasking Four Knapsack Problems in the Traveling Thief Benchmark — arXiv:2611.12597},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.12597},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4762ffd48e44; sha256 898e1c5f919c053bd60b7ff2c33a62f5d1c87aa89eeb5424613a5b4ff200c373},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.12597. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The traveling thief problem (TTP) asks a thief to choose a tour and a packing together, and the benchmark of 9,720 instances of Polyakovskiy et al. (2014) is the standard test set for comparing TTP heuristics. We show that four of these instances are not TTP instances at all. Their files give a renting rate of 0.00, so the tour has no effect on the objective and each instance reduces to a 0-1 knapsack problem. One of them belongs to the 60 categorized instances on which new methods are usually compared, and on it five of nine published methods report exactly the same value. The cause is the format of the files, which keep the renting rate with two decimals, while the rule of the generator gives a rate close to 0.003 on these instances. The same rounding may shift the rate of 949 other instances by more than 1%. Since the tour and the packing used by the generator were not published, the original rates cannot be recovered. We therefore define new rates with the same rule, applied to a fully specified reference solution that we publish, and we show with a published heuristic that the corrected instances behave as TTP instances again. We also give reference results on the corrected instances and recommendations for future studies. Finally, we present ttplib, a new open-source Python library that loads any of the 9,720 instances, including the corrected ones, without downloading the whole benchmark.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Computation and Language (cs.CL) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.12597 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-10T18:37:37.700Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).