A dynamic programming approach for solving nonlinear knapsack problems

Abstract

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 op-timal solution even in the case of discrete solution space for these problems. Despite the power of this solu-tion approach, it computationally performs very slowly when the solution space of the problems grows rap-idly. In this paper the authors developed a procedure for improving the computational efficiency of the dy-namic programming for solving KNP. They incorporate three routines; the imbedded state, surrogate con-straints, 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 pro-posed approach with the general dynamic programming approach is also presented.