The Traveling Thief Benchmark Has Four Broken Instances — and 949 More That Are Slightly Wrong

A data-hygiene audit finds that rounding in the canonical TTP benchmark silently converts four instances into plain knapsack problems, potentially contaminating a decade of heuristic comparisons.

Imagine you're scoring a decathlon, but someone accidentally zeroed out the scoring weight for the pole vault. Every athlete still runs and jumps, but the rankings now silently reflect nine events, not ten. Athletes who happened to be strong in the other nine events look better than they should, and nobody notices because the scorecard still says "decathlon." That's what happened to four instances in the most widely used traveling thief benchmark. The traveling thief problem (TTP) couples a tour-selection problem with a packing problem: the thief rents a vehicle, and the longer the tour, the more rent is paid — so the route and the items are interdependent. The benchmark of Polyakovskiy et al. (2014), containing 9,720 instances, is the canonical test set for every TTP heuristic published in the last decade. Alanazi and Khemakhem show that four of these instances have a renting rate of exactly 0.00 in the data files, which means the tour contributes nothing to the objective. Each of these four instances collapses into a standard 0–1 knapsack problem — a fundamentally easier, well-solved problem that the TTP was designed to go beyond. The root cause is mundane but consequential: the benchmark generator computes renting rates that, for these instances, land near 0.003, but the file format truncates to two decimal places, rounding to 0.00. One of the four broken instances sits inside the 60-instance subset commonly used for head-to-head comparisons of new methods. On that instance, five of nine published methods report exactly the same objective value — because they're all solving the same knapsack, and the tour is irrelevant. Any performance differences reported on this instance are noise, not signal. The damage extends beyond four instances. The same two-decimal truncation shifts the renting rate by more than 1% on 949 additional instances — roughly 10% of the entire benchmark. Because the original generator's internal tour and packing were never published, the true rates cannot be recovered. The authors propose a clean fix: recompute rates using the original formula applied to a fully specified reference solution that they publish. They verify with an existing heuristic that the corrected instances restore the coupling between tour and packing — they behave as TTP instances again. The practical deliverable is ttplib, an open-source Python library that loads any of the 9,720 instances (including corrected versions) without requiring the user to download the full benchmark. This is infrastructure-grade housekeeping: it lowers the friction for future researchers to use the corrected data and makes it harder to accidentally run experiments on broken instances. The broader lesson is one the optimization and ML communities keep relearning: benchmark integrity is not a side concern. When file-format rounding silently changes the problem class of your test instances, every leaderboard result built on those instances is suspect. The authors handle this with appropriate restraint — they don't claim published rankings are invalidated wholesale, but they demonstrate that at least one commonly used instance cannot distinguish methods that should be distinguishable. What's missing is scale of impact: we don't know how many published results would change if the corrected instances were substituted. That experiment — re-running published heuristics on the corrected benchmark — is the obvious next step, and the authors chose not to do it. Likely a scope decision: they provide the tools and leave the replication to the community.