American Institute of Mathematical Sciences

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

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

Jing Zhou 1, , Dejun Chen 1, , Zhenbo Wang 1, and  Wenxun Xing 1,

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.
Keywords: nonnegative quadratic function cone, conic approximation., 0-1 quadratic knapsack problem.
Mathematics Subject Classification: Primary: 90C10, 90C20, 90C2.
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, MPS/SIAM Series on Optimization, Philadelphia, 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-325. 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-575. 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-197. 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-139. 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-130. 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-149. 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-215. 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-795. 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-18. 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-1490. 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-793. 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-341. 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-22. 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-682. 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-648. 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-207. 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-267. 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, NBS Internal 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-339. 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, MPS/SIAM Series on Optimization, Philadelphia, 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-325. 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-575. 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-197. 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-139. 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-130. 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-149. 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-215. 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-795. 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-18. 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-1490. 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-793. 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-341. 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-22. 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-682. 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-648. 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-207. 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-267. 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, NBS Internal 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-339. 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]

Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048
[5]

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
[6]

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
[7]

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
[8]

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
[9]

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

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061
[16]

Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (70)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy