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