A dynamic programming approach for solving nonlinear knapsack problems
محورهای موضوعی : Mathematical OptimizationE Jahangiri 1 , F Ghassemi-Tari 2
1 - Assistant Professor, Islamic Azad University, Science and Research Branch, Tehran, Iran
2 - Associate Professor, Sharif University of Technology, Tehran, Iran
کلید واژه: Discrete optimization, Multiple-choice knapsack, Imbedded state, Surrogate constraint,
چکیده مقاله :
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.
