July  2013, 9(3): 531-547. doi: 10.3934/jimo.2013.9.531

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

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China, China, China, China

Received  February 2012 Revised  August 2012 Published  April 2013

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.
Citation: Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531
References:
[1]

A. Ben-Tal and A. Nemirovski, "Lectures On Modern Convex Optimization, Analysis, Algorithms and Engineering Applications,", $1^{st}$ edition, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar

[2]

A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operation Research, 92 (1996), 310.  doi: 10.1016/0377-2217(94)00229-0.  Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00244-3.  Google Scholar

[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.  doi: 10.1287/ijoc.1030.0029.  Google Scholar

[5]

A. Caprara, D. Pisinger and P. Toth, Exact solution of quadratic knapsack problem,, INFORMS Journal on Computing, 11 (1999), 125.  doi: 10.1287/ijoc.11.2.125.  Google Scholar

[6]

G. Dijkhuizen and U. Faigle, A cutting-plane approach to the edge-weighted maximal clique problem,, European Journal Operational Research, 69 (1993), 121.  doi: 10.1016/0377-2217(93)90097-7.  Google Scholar

[7]

G. Gallo, P. L. Hammer and B. Simeone, Quadratic knapsack problems,, Mathematical Programming Study, 12 (1980), 132.  doi: 10.1007/BFb0120892.  Google Scholar

[8]

D. J. Grainger and A. N. Letchford, "Improving a Formulation of the Quadratic Knapsack Problem,", Available from: , ().   Google Scholar

[9]

M. Grant and S. Boyed, CVX: Matlab software for disciplined convex programming, version 2.0(2012),, Available from: , ().   Google Scholar

[10]

C. Helmberg, F. Rendl and R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem,, Journal of Combinatorial Optimization, 4 (2000), 197.  doi: 10.1023/A:1009898604624.  Google Scholar

[11]

K. Holmström, A. O. Göran and M. M. Edvall, "User's Guide for Tomlab 7,", Available from: , ().   Google Scholar

[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.  doi: 10.1007/s00453-008-9248-1.  Google Scholar

[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.  doi: 10.1016/j.cor.2010.10.027.  Google Scholar

[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.  doi: 10.1137/100793955.  Google Scholar

[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).   Google Scholar

[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.  doi: 10.3934/jimo.2010.6.779.  Google Scholar

[17]

P. Michelon and L. Veilleux, Lagrangian methods for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 326.  doi: 10.1016/0377-2217(94)00286-X.  Google Scholar

[18]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-Hard,, Journal of Global Optimization, 1 (1991), 15.  doi: 10.1007/BF00120662.  Google Scholar

[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.  doi: 10.1016/0377-2217(95)00299-5.  Google Scholar

[20]

D. Pisinger, The quadratic knapsack problem-a survey,, Discrete Applied Mathematics, 155 (2007), 623.  doi: 10.1016/j.dam.2006.08.007.  Google Scholar

[21]

J. Rhys, A selection problem of shared fixed costs and network flows,, Management Science, 17 (1970), 200.  doi: 10.1287/mnsc.17.3.200.  Google Scholar

[22]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[23]

C. Witzgall, "Mathematical Methods of Site Selection for Electronic Message System(EMS),", Technical Report, (1975).   Google Scholar

[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.  doi: 10.1007/s10898-012-9872-9.  Google Scholar

show all references

References:
[1]

A. Ben-Tal and A. Nemirovski, "Lectures On Modern Convex Optimization, Analysis, Algorithms and Engineering Applications,", $1^{st}$ edition, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar

[2]

A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operation Research, 92 (1996), 310.  doi: 10.1016/0377-2217(94)00229-0.  Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00244-3.  Google Scholar

[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.  doi: 10.1287/ijoc.1030.0029.  Google Scholar

[5]

A. Caprara, D. Pisinger and P. Toth, Exact solution of quadratic knapsack problem,, INFORMS Journal on Computing, 11 (1999), 125.  doi: 10.1287/ijoc.11.2.125.  Google Scholar

[6]

G. Dijkhuizen and U. Faigle, A cutting-plane approach to the edge-weighted maximal clique problem,, European Journal Operational Research, 69 (1993), 121.  doi: 10.1016/0377-2217(93)90097-7.  Google Scholar

[7]

G. Gallo, P. L. Hammer and B. Simeone, Quadratic knapsack problems,, Mathematical Programming Study, 12 (1980), 132.  doi: 10.1007/BFb0120892.  Google Scholar

[8]

D. J. Grainger and A. N. Letchford, "Improving a Formulation of the Quadratic Knapsack Problem,", Available from: , ().   Google Scholar

[9]

M. Grant and S. Boyed, CVX: Matlab software for disciplined convex programming, version 2.0(2012),, Available from: , ().   Google Scholar

[10]

C. Helmberg, F. Rendl and R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem,, Journal of Combinatorial Optimization, 4 (2000), 197.  doi: 10.1023/A:1009898604624.  Google Scholar

[11]

K. Holmström, A. O. Göran and M. M. Edvall, "User's Guide for Tomlab 7,", Available from: , ().   Google Scholar

[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.  doi: 10.1007/s00453-008-9248-1.  Google Scholar

[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.  doi: 10.1016/j.cor.2010.10.027.  Google Scholar

[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.  doi: 10.1137/100793955.  Google Scholar

[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).   Google Scholar

[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.  doi: 10.3934/jimo.2010.6.779.  Google Scholar

[17]

P. Michelon and L. Veilleux, Lagrangian methods for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 326.  doi: 10.1016/0377-2217(94)00286-X.  Google Scholar

[18]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-Hard,, Journal of Global Optimization, 1 (1991), 15.  doi: 10.1007/BF00120662.  Google Scholar

[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.  doi: 10.1016/0377-2217(95)00299-5.  Google Scholar

[20]

D. Pisinger, The quadratic knapsack problem-a survey,, Discrete Applied Mathematics, 155 (2007), 623.  doi: 10.1016/j.dam.2006.08.007.  Google Scholar

[21]

J. Rhys, A selection problem of shared fixed costs and network flows,, Management Science, 17 (1970), 200.  doi: 10.1287/mnsc.17.3.200.  Google Scholar

[22]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[23]

C. Witzgall, "Mathematical Methods of Site Selection for Electronic Message System(EMS),", Technical Report, (1975).   Google Scholar

[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.  doi: 10.1007/s10898-012-9872-9.  Google Scholar

[1]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[2]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125

[3]

Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223

[4]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[5]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[6]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269

[7]

Xiaoling Sun, Xiaojin Zheng, Juan Sun. A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 47-60. doi: 10.3934/jimo.2009.5.47

[8]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795

[9]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[10]

Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59

[11]

Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945

[12]

Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129

[13]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2019061

[14]

Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237

[15]

Shigeaki Koike, Hiroaki Morimoto, Shigeru Sakaguchi. A linear-quadratic control problem with discretionary stopping. Discrete & Continuous Dynamical Systems - B, 2007, 8 (2) : 261-277. doi: 10.3934/dcdsb.2007.8.261

[16]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[17]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[18]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[19]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[20]

Konstantinos A. Draziotis, Anastasia Papadopoulou. Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme. Advances in Mathematics of Communications, 2018, 12 (3) : 429-449. doi: 10.3934/amc.2018026

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]