1
Assistant Professor, Islamic Azad University, Science and Research Branch, Tehran, Iran
2
Associate Professor, Sharif University of Technology, Tehran, Iran
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.
Jahangiri, E., Ghassemi-Tari, F. (2006). A dynamic programming approach for solving nonlinear knapsack problems. Journal of Industrial Engineering, International, 2(2), 31-37.
MLA
E Jahangiri; F Ghassemi-Tari. "A dynamic programming approach for solving nonlinear knapsack problems". Journal of Industrial Engineering, International, 2, 2, 2006, 31-37.
HARVARD
Jahangiri, E., Ghassemi-Tari, F. (2006). 'A dynamic programming approach for solving nonlinear knapsack problems', Journal of Industrial Engineering, International, 2(2), pp. 31-37.
VANCOUVER
Jahangiri, E., Ghassemi-Tari, F. A dynamic programming approach for solving nonlinear knapsack problems. Journal of Industrial Engineering, International, 2006; 2(2): 31-37.
)