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]

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

Metrics

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

Other articles
by authors

[Back to Top]