Simple solution methods for separable mixed linear and quadratic knapsack problem
Simple solution methods for separable mixed linear and quadratic knapsack problem
复制标题
可分离混合线性二次背包问题的简单求解方法
DOI：
10.1016/j.apm.2011.10.017
复制
发表时间：
2012-07
影响因子：
5
通讯作者：
Hua, Zhongsheng
中科院分区：
文献类型：
--
作者：
Zhang, Bin;Hua, Zhongsheng
Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers.
登录
查看更多内容
影响因子：
4.8
作者：
L. Fernandes;A. Fischer;J. Júdice;Cristina Requejo;João L. C. Soares
通讯作者：
L. Fernandes;A. Fischer;J. Júdice;Cristina Requejo;João L. C. Soares
影响因子：
6.4
作者：
A. Billionnet;Frédéric Calmels
通讯作者：
A. Billionnet;Frédéric Calmels
DOI：
10.1016/0167-6377(95)00009-9
发表时间：
1995-04
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
D. Hochbaum
通讯作者：
D. Hochbaum
DOI：
10.1287/opre.46.2.272
发表时间：
1998-02
期刊：
Oper. Res.
影响因子：
--
作者：
M. Kodialam;H. Luss
通讯作者：
M. Kodialam;H. Luss
DOI：
10.1016/s0377-2217(03)00244-3
发表时间：
2004-09
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
A. Billionnet;Éric Soutif
通讯作者：
A. Billionnet;Éric Soutif