摘要
对于一类带有单个线性约束以及盒约束的一般连续可分离二次背包问题给出了一种直接的算法,根据模型特有的结构,通过调节线性约束的拉格朗日乘子λ的取值范围,以及在算法求解过程中通过判断目标函数一次项中的变量是否在盒约束范围内,来逐步确定所有变量的最优值,并通过该算法得到的实验结果与其他算法的比较,说明了这种算法的可行性和有效性.
The quadratic Knapsack problem is NP-hard. In this paper, a direct algorithm is proposed for an ordinary continuous separable quadratic Knapsack problem with a single linear constraint and box constrains. According to the special structure model, the optimal value of all the variables can be fixed gradually by adjusting the range of the Lagrangian multiplier for the linear constrain and by judging whether the variables of the first power in the objective function satisfy the box constraints. Finally the feasibility and efficiency of the algorithm are illustrated through the comparison of experimental results.
出处
《运筹学学报》
CSCD
北大核心
2013年第1期44-58,共15页
Operations Research Transactions
关键词
二次背包问题
可分离
拉格朗日乘子
盒约束
quadratic Knapsack problem, separable, Lagrangian multiplier, box con- strains
