File(s) under permanent embargo

On the impact of the renting rate for the unconstrained nonlinear Knapsack problem

conference contribution
posted 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 [4], 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.



Genetic and evolutionary computation. Conference (2016 : Denver, Colorado)


413 - 419




Denver, Colorado

Place of publication

New York, N.Y.

Start date


End date






Publication classification

E Conference publication; E1.1 Full written paper - refereed

Copyright notice

2016, ACM

Title of proceedings

GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference