An Algorithm for Nonlinear Knapsack Problems

Thomas L. Morin and Roy E. Marsten
Additional contact information
Thomas L. Morin: The Technological Institute, Northwestern University
Roy E. Marsten: Sloan School of Management, Massachusetts Institute of Technology

Management Science, 1976, vol. 22, issue 10, 1147-1158

Abstract: 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.

Date: 1976
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.22.10.1147 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:22:y:1976:i:10:p:1147-1158

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().