A dynamic programming approach for solving nonlinear knapsack problems.

Nonlinear Knapsack Problems (NKP) are the alternative formulation for the multiple-choice knapsack problems. A powerful approach for solving NKP is dynamic programming which may obtain the global optimal solution even in the case of discrete solution space for these problems. Despite the power of this solution approach, it computationally performs very slowly when the solution space of the problems grows rapidly. In this paper the authors developed a procedure for improving the computational efficiency of the dynamic programming for solving KNP. They incorporate three routines; the imbedded state, surrogate constraints, and bounding scheme, in the dynamic programming solution approach and developed an algorithmic routine for solving the KNP. An experimental study for comparing the computational efficiency of the proposed approach with the general dynamic programming approach is also presented.