A dynamic programming approach for solving nonlinear knapsack problems

Subject Areas : Mathematical Optimization

E Jahangiri ¹ , F Ghassemi-Tari ²

1 - Assistant Professor, Islamic Azad University, Science and Research Branch, Tehran, Iran
2 - Associate Professor, Sharif University of Technology, Tehran, Iran

Received: 2015-05-19 Accepted : 2015-05-19 Published : 2006-03-01

Keywords: Discrete optimization, Multiple-choice knapsack, Imbedded state, Surrogate constraint,

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.