Heuristic and Exact Solution Method for Convex nonlinear Knapsack Problem
Heuristic and Exact Solution Method for Convex nonlinear Knapsack Problem
复制标题
DOI：
10.1142/s0217595912500315
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Bin Zhang;Bo Chen
中科院分区：
文献类型：
--
作者：
Bin Zhang;Bo Chen
本文考虑了一类决策变量均为整数、目标函数和背包函数均为非线性的凸非线性背包问题。这个广义问题的特点是正边际成本（PMC）和递增边际损失成本比（IMLCR）。通过分析问题的结构特征，提出了一种有效的启发式算法，并提出了搜索和分支规则，改进了求解精确解的分支定界法。数值实验表明了该启发式算法和改进的分支定界法的有效性。
In this paper, we consider a class of convex nonlinear knapsack problems in which all decision variables are integer and the objective and knapsack functions are nonlinear. This generalized problem is characterized by positive marginal cost (PMC) and increasing marginal loss-cost ratio (IMLCR). By analyzing the structural properties of the problem, we develop an efficient heuristic and propose search and branching rules to improve the branch and bound method for solving exact solution. Numerical study is done for showing the effectiveness of the proposed heuristic and the modified branch and bound method.