An Algorithm for Nonlinear Knapsack Problems.

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