Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108326
Citations | ||
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 1611-3349 |
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 Responsibility: | 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: | http://purl.org/au-research/grants/arc/DP130104395 |
Published version: | http://dx.doi.org/10.1007/978-3-319-18008-3_23 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_108326.pdf Restricted Access | Restricted Access | 317.89 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.