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.
While traditional optimization problems were often studied in isolation, many real-world problems today require interdependence among multiple optimization components. The traveling thief problem (TTP) is a multi-component problem that has been widely studied in the literature. In this paper, we introduce and investigate the TTP with time window constraints which provides a TTP variant highly relevant to real-world situations where good can only be collected at given time intervals. We examine adaptions of existing approaches for TTP and the Traveling Salesperson Problem (TSP) with time windows to this new problem and evaluate their performance. Furthermore, we provide a new heuristic approach for the TTP with time windows. To evaluate algorithms for TTP with time windows, we introduce new TTP benchmark instances with time windows based on TTP instances existing in the literature. Our experimental investigations evaluate the different approaches and show that the newly designed algorithm outperforms the other approaches on a wide range of benchmark instances.
Helen Yuliana Angmalisang, Frank Neumann
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, SA 5000
The travelling thief problem (TTP) is a well-known multi-component optimisation problem that captures the interdependence between two components: the tour across cities and the packing of items. The packing while travelling problem (PWT) is an NP-hard subproblem of TTP where the packing of items should be optimised for a given fixed tour. In many solvers, the packing component is often addressed using greedy heuristics. Here, the use of suitable greedy functions is essential for the success of greedy algorithms. In this paper, we introduce new reward functions tailored to the PWT and extend them to a hyper-heuristic framework to achieve further advantage. Furthermore, we investigate the chance constrained PWT for greedy approaches and adopt the newly introduced reward functions for stochastic weights. The experimental results clearly demonstrate the benefit of the tailored heuristics over the standard heuristics in both deterministic and stochastic constraints.
Thilina Pathirage Don, Aneta Neumann, Frank Neumann
Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia
Neural routing solvers sample many solutions per instance and keep the best, with the same number of samples for every instance. We measure how much a non-uniform split of the same total budget is worth and which property of a workload decides it. Best-of-k curves estimated by averaging random orderings of stored samples overstate the gain, and deciding on one half of the samples while evaluating on the other understates it; we use exact best-of-k curves, a U-statistic over all orderings. For three pretrained solvers (POMO, the Attention Model and Sym-NCO) on the traveling salesman problem, reallocation reduces the total optimality gap by at most 2.5% on the training distribution, so uniform allocation is close to optimal there. On workloads that mix in out-of-distribution instances it reduces the gap by 11.8-13.3% (1.1-1.8% of tour length) for the two solvers that degrade under the shift, and almost nothing for the one that does not. Across two heterogeneity mechanisms, three solvers, two confirmation collections and budgets of 25 to 200 samples per instance, the gain is predicted by the spread of difficulty within a workload, not its average. Allocating on a power-law curve fitted to twenty charged probe samples per instance recovers 88-93% of the uncharged optimum; successive halving does worse. A 2-opt local search, however, removes most of the gap at negligible cost, after which reallocation adds a few hundredths of a percent of tour length.
Jinhyung Bae
Department of Industrial and Management Engineering / AI Data Convergence, Hankuk University of Foreign Studies, Yongin, Republic of Korea.