Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: On the impact of the renting rate for the unconstrained nonlinear Knapsack problem
Author: Wu, J.
Polyakovskiy, S.
Neumann, F.
Citation: Proceedings of the 2016 Genetic and Evolutionary Computation Conference, 2016 / pp.413-419
Publisher: ACM
Issue Date: 2016
ISBN: 9781450342063
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (20 Jul 2016 - 24 Jul 2016 : Denver, CO)
Statement of
Junhua Wu, Sergey Polyakovskiy, Frank Neumann
Abstract: 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.
Keywords: Traveling thief problem; non-linear knapsack problem; trans- portation; combinatorial optimisation
Rights: © 2016 ACM
RMID: 0030054779
DOI: 10.1145/2908812.2908862
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_108330.pdfRestricted Access994.99 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.