Accession Number : AD0780929
Title : An Algorithm for Nonlinear Knapsack Problems.
Descriptive Note : Technical rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER
Personal Author(s) : Marsten,Roy E. ; Morin,Thomas L.
Report Date : MAY 1974
Pagination or Media Count : 30
Abstract : A recursive algorithm for the solution of separable nonlinear multidimensional knapsack problems is developed by exploiting discontinuity preserving properties of the maximal convolution. The curse of dimensionality, which is usually associated with dynamic programming type algorithms, is successfully mitigated by reducing an M-dimensional dynamic program to a 1-dimensional dynamic program through the use of the imbedded state space approach. Computational experience with the algorithm on problems with as many as 10 state variables is also reported and several interesting extensions are discussed. (Author)
Descriptors : *Dynamic programming, Integer programming, Set theory, Algorithms
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE