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.
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
Instance
Capacity
Optimal profit
Items packed
dsj1000_n999_bounded-strongly-corr_01
87,826
144,426
291
dsj1000_n999_uncorr-similar-weights_01
91,232
85,721
90
dsj1000_n999_uncorr-similar-weights_02
182,464
164,663
181
dsj1000_n999_uncorr_01
45,302
165,552
257
Table 1: The four instances with R=0.00 .
Method
Source of the value
Value
CoCo +
Namazi et al. (2023)
144,426
CoCo
Namazi et al. (2019)
144,219
CS2SA
El Yafrani and Ahiod (2016)
144,219
MA2B
El Yafrani and Ahiod (2016)
144,219
CS2SA ∗
El Yafrani and Ahiod (2018)
144,219
SAVI
Nguyen et al. (2023)
144,219
Table 2: Published values on dsj1000_n999_bounded-strongly-corr_01.
Figure 1: How the rent of dsj1000_n999_bounded-strongly-corr_01 becomes zero in the files (top), and how this note defines its new rent (bottom, Section 3.2 ).
Capacity level
Type of knapsack
01
02
03
04
05
06
07
08
09
10
bounded strongly correlated
0.00
0.01
0.01
0.01
0.01
0.01
0.02
0.02
0.02
0.02
uncorrelated, similar weights
0.00
0.00
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
uncorrelated
0.00
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
Table 3: Rents in the files of dsj1000 with 999 items, by type of knapsack and capacity level.
Figure 2: The 9,720 instances by relative rounding half-width q (logarithmic vertical axis).
Instance
Smallest R
Largest R
dsj1000_n999_bounded-strongly-corr_01
0.002836
0.003295
dsj1000_n999_uncorr-similar-weights_01
0.001736
0.001875
dsj1000_n999_uncorr-similar-weights_02
0.003298
0.003683
dsj1000_n999_uncorr_01
0.003325
0.003540
Table 4: Rents given by rule ( 3 ) on ten linkern tours.
Instance
Travel time
New R
dsj1000_n999_bounded-strongly-corr_01
50,822,606
0.00284177
dsj1000_n999_uncorr-similar-weights_01
45,714,939
0.00187512
dsj1000_n999_uncorr-similar-weights_02
44,709,234
0.00368298
dsj1000_n999_uncorr_01
47,522,162
0.00348368
Table 5: New rents of the four instances.
Original file
Corrected file
Instance (dsj1000, 999 items)
Value
Min
Mean
Max
Std. dev.
Items picked
bounded strongly corr., 01
144,219
66,533
66,865
67,119
184
220 to 246
similar weights, 01
85,719
33,100
33,463
34,145
322
90
similar weights, 02
164,660
50,950
51,458
52,271
507
181
uncorrelated, 01
165,494
57,036
57,187
57,535
165
233 to 234
Table 6: Results of CoCo + on the original and the corrected files.
Figure 3: How ttplib serves an instance (top), and an example of use with its output (bottom).
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.