A unified method for a class of convex separable nonlinear knapsack problems

作者：Zhang Bin; Hua Zhongsheng^*

来源：European Journal of Operational Research, 2008, 191(1): 1-6.

DOI：10.1016/j.ejor.2007.07.005

• nonlinear knapsack problem
• convex programming
• separable programming
• singly constrained program

In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss-cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush-Kuhn-Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems.

• 出版日期2008-11-16
• 单位中国科学技术大学