一类连续可分离背包问题的直接算法

运筹学学报 ›› 2013, Vol. 17 ›› Issue (1): 44-58.

一类连续可分离背包问题的直接算法

朱婷婷¹，陈伟¹，陈娟娟¹，孙文浩¹

1. 上海大学理学院

出版日期:2013-03-15 发布日期:2013-03-15
通讯作者: 陈伟 E-mail:chenwei@staff.shu.edu.cn

Direct algorithm for continuous separable Knapsack problem

ZHU Tingting¹, CHEN Wei¹, CHEN Juanjuan¹, SUN Wenhao¹

1. College of Science, Shanghai University

Online:2013-03-15 Published:2013-03-15

摘要/Abstract

摘要： 对于一类带有单个线性约束以及盒约束的一般连续可分离二次背包问题给出了一种直接的算法，根据模型特有的结构，通过调节线性约束的拉格朗日乘子λ 的取值范围，以及在算法求解过程中通过判断目标函数一次项中的变量是否在盒约束范围内，来逐步确定所有变量的最优值, 并通过该算法得到的实验结果与其他算法的比较，说明了这种算法的可行性和有效性．

关键词: 二次背包问题, 可分离, 拉格朗日乘子, 盒约束

Abstract: 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.

Key words: quadratic Knapsack problem, separable, Lagrangian multiplier, box constrains

朱婷婷，陈伟，陈娟娟，孙文浩. 一类连续可分离背包问题的直接算法[J]. 运筹学学报, 2013, 17(1): 44-58.

ZHU Tingting, CHEN Wei, CHEN Juanjuan, SUN Wenhao. Direct algorithm for continuous separable Knapsack problem[J]. Operations Research Transactions, 2013, 17(1): 44-58.

参考文献

Bernhard R H. Mathematical programming models for captial budgeting---a survey generalization and critique [J].   Journals of Financia lquarterly Analysis, 1969, 4: 111-158.
Bernhard R H. Mathematical programming models for captial budgeting---a survey generalization and critique [J]. Journals of Financia lquarterly Analysis, 1969, 4: 111-158.
黄红选, 韩继业. 数学规划 [M]. 北京：清华大学出版社, 2006.
Bretthauer K M, Shetty B. Quadratic resource allocation with generalized upper bounds [J]. Oper Res Lett, 1997,   20: 51-57.
Bretthauer K M, Shetty B. The nonlinear resource allocation problem [J].   Operations Research,   1995, 43: 670-683.
Bitran G R, Hax A C. Disaggregation and resource allocation using convex knapsack problems with bounded variables [J]. Management Science, 1981, 27: 431-441.
黄红选. 运筹学：数学规划 [M]. 北京：清华大学出版社, 2011.
Bitran G R, Hax A C. Disaggregation and resource allocation using convex knapsack problems with bounded variables [J]. Manag Sci, 1981, 27: 431-441.
Caprara A, Pisinger D, Toth P. Exact solution of the quadratic knapsack problem [J]. INPORMS Journal on Computing, 1999, 11: 125-137.
Chu P C, Beasley J E. A genetic algorithm for the multidimensional knapsack problem [J].   Journal of Heuristics, 1998, 4: 63-86.
Bretthauer K M, Shetty B, Syam S. A branch and bound algorithm for integer quadratic knapsack problems [J]. ORSA Journal on Computing, 1995, 7(1): 109-118.
Kiwiel K C. Variable fixing algorithms for the continuous quadratic knapsack problem [J]. Journal of Optimization Theory and Applications, 2008, 136: 445-458.
Mathur K, Salkin H M, Morito S. A branch and search algorithm for a class of nonlinear knapsack problems [J]. Operations Research Letters, 1983, 2: 155-60.
Jorge J M, Stephen A V. On the solution of concave knapsack problems [J].   Mathmatical Programming, 1991, 49: 397-411.
Robinson A G, Jiang N, Lerme C S. On the continuous quadratic knapsack problem [J]. Mathematical Programming, 1992, 55: 99-108.
Guder F,   Morris J G. Optimal objective function approximation for separable convex quadratic programming [J]. Mathematical Programming, 1994, 67: 133-142.
华中生, 张斌. 求解可分离连续凸二次背包问题的直接算法 [J]. 系统工程与电子技术, 2005, 27(2): 331-334.
Rosen J B, Pardalos P M. Global minimization of large-scale constrained concave quadratic problems by separable programming [J].   Math Program, 1986, 34: 163-174.
Rosen J B, Pardalos P M. Global minimization of large-scale constrained concave quadratic problems by separable programming [J]. Math Program, 1986, 34: 163-174.
任燕, 陈伟. 可分离的二次背包问题的一种直接算法 [J]. 上海大学学报, 2010, 4: 387-393.
Li J L,   Wang P, Ma L. A new algorithm for the general quadratic programming problems with box constraints [J]. Original Paper, 2010, 55: 79-85.
Zhang X J,   Sun X L, Li D. Separable relaxation for nonconvex quadratic integer programming:integer diagonalization approach [J]. Optim Theory Appl, 2010, 146: 463-489.
Pardalos P M, Kovoor N. An algorithm for a singly constrained class of Quadratic programs subject to upper and lower bounds [J].   Mathematical Programming, 1990, 46: 321-328.
Horst R, Thoai N V. An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks [J]. OR Spektrum, 1998, 20: 47-53.
Stefan M. Stefanov. Convex seperable minimization subject to bounded variables [J]. Computational Optimization and Applications, 2001, 18: 27-48.
Bretthauer K M, Shetty B. The nonlinear knapsack problem---algorithms and applications [J].   European Journal of Operations Research, 2002, 138: 459-472.
Bretthauer K M, Shetty B. A pegging algorithm for the nonlinear resource allocation problem [J]. Computers Operations Research, 2002, 29: 505-527.