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, (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]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[2]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[3]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[4]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[5]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[6]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[7]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[8]

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[9]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[10]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[11]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[12]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[13]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[14]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[15]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379
[16]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[17]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[18]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[19]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[20]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences