An Algorithm for Nonlinear Knapsack Problems

An algorithm which recursively generates the complete family of undominated feasible solutions to separable nonlinear multidimensional knapsack problems is developed by exploiting discontinuity preserving properties of the maximal convolution. The "curse of dimensionality," which is usuall...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1976-06, Vol.22 (10), p.1147-1158
Main Authors: Morin, Thomas L, Marsten, Roy E
Format: Article
Language:English
Subjects:
Algorithms
Capital budgeting
Dimensionality
Dynamic programming
Gin
Integer programming
Integers
Knapsack problem
Management science
Mathematical functions
Mathematical vectors
Optimal solutions
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An algorithm which recursively generates the complete family of undominated feasible solutions to 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 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.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.22.10.1147