File(s) under permanent embargo
On the impact of the renting rate for the unconstrained nonlinear Knapsack problem
conference contributionposted on 2016-07-20, 00:00 authored by J Wu, Sergey PolyakovskiySergey Polyakovskiy, F Neumann
© 2016 ACM. Multi-component problems combine several combinatorial optimisation problems that occur frequently in real-word applications such as logistics and supply chain management. In order to study the impact of the combination of such problems, the traveling thief problem , which combines the traveling salesman problem and the 0-1 knapsack problem, has been introduced. Recently, it has been shown that the non-linear knapsack problem constituting the packing component of the traveling thief problem is NP-hard even when the capacity constraint is not imposed. We investigate the role of the renting rate R which is an important parameter in combining the total profit of selected items and the associated transportation costs in this non-linear knapsack problem. Our theoretical and experimental investigations show how the values of the renting rate influence the difficulty of a given problem instance through the items that can be excluded by a simple but very effective pre-processing scheme. Our further investigations show how to create instances that are hard to be solved by simple evolutionary algorithms.