Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Packing while traveling: mixed integer programming for a class of nonlinear knapsack problems
Author: Polyakovskiy, S.
Neumann, F.
Citation: Lecture Notes in Artificial Intelligence, 2015 / Michel, L. (ed./s), vol.9075, pp.332-346
Publisher: Springer
Issue Date: 2015
Series/Report no.: Lecture Notes in Computer Science
ISBN: 9783319180076
ISSN: 0302-9743
Conference Name: 12th International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming (CPAIOR) (18 May 2015 - 22 May 2015 : Barcelona, Spain)
Editor: Michel, L.
Statement of
Sergey Polyakovskiy and Frank Neumann
Abstract: Packing and vehicle routing problems play an important role in the area of supply chain management. In this paper, we introduce a non-linear knapsack problem that occurs when packing items along a fixed route and taking into account travel time. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. In order to solve the problems, we provide a pre-processing scheme as well as exact and approximate mixed integer programming (MIP) solutions. Our experimental results show the effectiveness of the MIP solutions and in particular point out that the approximate MIP approach often leads to near optimal results within far less computation time than the exact approach.
Keywords: Non-linear knapsack problem; NP-hardness; Mixed integer programming; Linearization technique; Approximation technique
Description: LNCS 9075
Rights: © Springer International Publishing Switzerland 2015
DOI: 10.1007/978-3-319-18008-3_23
Grant ID:
Published version:
Appears in Collections:Aurora harvest 3
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access317.89 kBAdobe PDFView/Open

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