%0 Journal Article
%T A dynamic programming approach for solving nonlinear knapsack problems
%J Journal of Industrial Engineering, International
%I Islamic Azad University, South Tehran Branch
%Z 1735-5702
%A Jahangiri, E
%A Ghassemi-Tari, F
%D 2006
%\ 03/01/2006
%V 2
%N 2
%P 31-37
%! A dynamic programming approach for solving nonlinear knapsack problems
%K Discrete optimization
%K Multiple-choice knapsack
%K Imbedded state
%K Surrogate constraint
%R
%X 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.
%U http://jiei.azad.ac.ir/article_511104_29da3d9116528f4b8a58e3f14dc9bdf7.pdf