File(s) under permanent embargo
Packing while traveling: mixed integer programming for a class of nonlinear knapsack problems
conference contribution
posted on 2015-01-01, 00:00 authored by Sergey PolyakovskiySergey Polyakovskiy, F NeumannPacking 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.
History
Event
Constraint Programming, Artificial Intelligence, and Operations Research. Conference (12th : 2015 : Barcelona, Spain)Volume
9075Series
Constraint Programming, Artificial Intelligence, and Operations Research ConferencePagination
332 - 346Publisher
SpringerLocation
Barcelona, SpainPlace of publication
Cham, SwitzerlandPublisher DOI
Start date
2015-05-18End date
2015-05-22ISSN
0302-9743eISSN
1611-3349ISBN-13
9783319180076Language
engPublication classification
E Conference publication; E1.1 Full written paper - refereedCopyright notice
2015, Springer International Publishing SwitzerlandEditor/Contributor(s)
Laurent MichaelTitle of proceedings
CPAIOR 2015 : Proceedings of the 12th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint ProgrammingUsage metrics
Categories
No categories selectedKeywords
Non-linear knapsack problemNP-hardnessMixed integer programmingLinearization techniqueApproximation techniqueScience & TechnologyTechnologyPhysical SciencesComputer Science, Artificial IntelligenceComputer Science, Theory & MethodsOperations Research & Management ScienceMathematics, AppliedRoboticsComputer ScienceMathematicscs.DS
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC