cs.CLNov 9, 2026

Unmasking Four Knapsack Problems in the Traveling Thief Benchmark

Authors: Mohammed Mizan Alanazi, Mahdi Khemakhem

Organizations: Department of Computer Science, College of Computer Engineering and Sciences, Prince Sattam bin Abdulaziz University, AlKharj, 11942, Saudi Arabia. · National School of Electronics and Telecommunications of Sfax (ENET’Com), University of Sfax, Sfax, Tunisia. · Data Engineering and Semantics Research Unit, Faculty of Sciences of Sfax, University of Sfax, Sfax, Tunisia.

Abstract

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.

Figures & tables

Explore similar work

CardsList
  1. The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

    Apr 8, 2026Helen Yuliana Angmalisang, Frank NeumannCombinatorial Optimization

  2. Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

    Apr 15, 2026Thilina Pathirage Don, Aneta Neumann, Frank NeumannGreedy OptimizationCombinatorial Optimization

  3. When Does Reallocating a Sampling Budget Pay? Instance-wise Allocation for Neural Routing Solvers

    Aug 21, 2026Jinhyung BaeInference-Time Compute AllocationNeural Combinatorial Optimization