A conic approximation method for the 0-1 quadratic knapsack problem

Jing Zhou; Dejun Chen; Zhenbo Wang; Wenxun Xing

doi:10.3934/jimo.2013.9.531

Article Contents

2013, Volume 9, Issue 3: 531-547. Doi: 10.3934/jimo.2013.9.531

This issue Previous Article Strong duality theorem for multiobjective higher order nondifferentiable symmetric dual programs Next Article American type geometric step options

A conic approximation method for the 0-1 quadratic knapsack problem

1.
Department of Mathematical Sciences, Tsinghua University, Beijing, 100084

Received: January 31, 2012

Revised: July 31, 2012

Published: June 2013

Abstract Related Papers Cited by

Abstract

This paper solves the 0-1 quadratic knapsack problem using a conic approximation method. We propose a nonnegative quadratic function cone program to equivalently represent the problem. Based on the technique of linear matrix inequality, we present an adaptive approximation scheme to obtain a global optimal solution or lower bound for the problem by using computable cones. Some computational examples are provided to show the effectiveness of the proposed method.

Keywords:

Mathematics Subject Classification: Primary: 90C10, 90C20, 90C22.

Citation:

Related Papers

Cited by

References

[1]	A. Ben-Tal and A. Nemirovski, "Lectures On Modern Convex Optimization, Analysis, Algorithms and Engineering Applications," $1^{st}$ edition, MPS/SIAM Series on Optimization, Philadelphia, 2001.doi: 10.1137/1.9780898718829.
[2]	A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operation Research, 92 (1996), 310-325.doi: 10.1016/0377-2217(94)00229-0.
[3]	A. Billionnet and E. Soutif, An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 157 (2004), 565-575.doi: 10.1016/S0377-2217(03)00244-3.
[4]	A. Billionnet and E. Soutif, Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem, INFORMS Journal on Computing, 16 (2004), 188-197.doi: 10.1287/ijoc.1030.0029.
[5]	A. Caprara, D. Pisinger and P. Toth, Exact solution of quadratic knapsack problem, INFORMS Journal on Computing, 11 (1999), 125-139.doi: 10.1287/ijoc.11.2.125.
[6]	G. Dijkhuizen and U. Faigle, A cutting-plane approach to the edge-weighted maximal clique problem, European Journal Operational Research, 69 (1993), 121-130.doi: 10.1016/0377-2217(93)90097-7.
[7]	G. Gallo, P. L. Hammer and B. Simeone, Quadratic knapsack problems, Mathematical Programming Study, 12 (1980), 132-149.doi: 10.1007/BFb0120892.
[8]	D. J. Grainger and A. N. Letchford, "Improving a Formulation of the Quadratic Knapsack Problem," Available from: http://www.optimization-online.org/DB_HTML/2007/06/1678.html.
[9]	M. Grant and S. Boyed, CVX: Matlab software for disciplined convex programming, version 2.0(2012), Available from: http://cvxr.com/cvx.
[10]	C. Helmberg, F. Rendl and R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem, Journal of Combinatorial Optimization, 4 (2000), 197-215.doi: 10.1023/A:1009898604624.
[11]	K. Holmström, A. O. Göran and M. M. Edvall, "User's Guide for Tomlab 7," Available from: http://tomopt.com/tomlab/.
[12]	H. Kellerer and V. A. Strusevich, Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications, Algorithmica, 57 (2010), 769-795.doi: 10.1007/s00453-008-9248-1.
[13]	L. Létocart, A. Nagih and G. Plateau, Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem, Computers and Operations Research, 39 (2012), 12-18.doi: 10.1016/j.cor.2010.10.027.
[14]	C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, SIAM Journal on Optimization, 21 (2011), 1475-1490.doi: 10.1137/100793955.
[15]	C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, Adaptive computable approximation to cones of nonnegative quadratic functions, Submitted to Optimization, (2011).
[16]	C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 6 (2010), 779-793.doi: 10.3934/jimo.2010.6.779.
[17]	P. Michelon and L. Veilleux, Lagrangian methods for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92 (1996), 326-341.doi: 10.1016/0377-2217(94)00286-X.
[18]	P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-Hard, Journal of Global Optimization, 1 (1991), 15-22.doi: 10.1007/BF00120662.
[19]	K. Park, K. Lee and S. Park, An extended formulation approach to the edge-weighted maximal clique problem, European Journal of Operational Research, 95 (1996), 671-682.doi: 10.1016/0377-2217(95)00299-5.
[20]	D. Pisinger, The quadratic knapsack problem-a survey, Discrete Applied Mathematics, 155 (2007), 623-648.doi: 10.1016/j.dam.2006.08.007.
[21]	J. Rhys, A selection problem of shared fixed costs and network flows, Management Science, 17 (1970), 200-207.doi: 10.1287/mnsc.17.3.200.
[22]	J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.doi: 10.1287/moor.28.2.246.14485.
[23]	C. Witzgall, "Mathematical Methods of Site Selection for Electronic Message System(EMS)," Technical Report, NBS Internal Report, 1975.
[24]	X. J. Zheng, X. L. Sun and D. Li, On the reduction of duality gap in quadratic knapsack problems, Journal of Global Optimization, 54 (2012), 325-339.doi: 10.1007/s10898-012-9872-9.