A dynamic programming approach for solving nonlinear knapsack problems

Journal of Industrial Engineering International

مقاله 3، دوره 2، شماره 2، خرداد 2006، صفحه 31-37   

نویسندگان

E Jahangiri¹؛ F Ghassemi-Tari^{* 2}

¹Assistant Professor, Islamic Azad University, Science and Research Branch, Tehran, Iran

²Associate Professor, Sharif University of Technology, Tehran, Iran

چکیده

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.

کلیدواژه‌ها

Discrete optimization؛ Multiple-choice knapsack؛ Imbedded state؛ Surrogate constraint