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