A Semidefinite Programming Approach to the Quadratic Knapsack Problem

• E. Balas, “Disjunctive programming: Cutting planes from logical conditions,” in Nonlinear Programming, vol. 2, O.L. Mangasarian et al. (Eds.), Academic Press, 1975a, pp. 279–312.

• E. Balas, “Facets of the knapsack polytope,” Mathematical Programming, vol. 8, pp. 146–164, 1975b.

  Google Scholar 

• E. Balas, S. Ceria, and G. Cornuejols, “A lift-and-project cutting plane algorithm for mixed 0=1 programs,” Mathematical Programming, vol. 58, pp. 295–324, 1993.

  Google Scholar 

• E. Balas, S. Ceria, G. Cornuejols, and G. Pataki, “Updated semi-definite constraints,” Technical Report, Carnegie Mellon University, Pittsburgh, USA, 1994.

  Google Scholar 

• S. Benson, Y. Ye, and X. Zhang, “Solving large-scale sparse semidefinite programs for combinatorial optimization,” Working paper, Department of Management Science, University of Iowa, IA, 52242, USA, Sept. 1997.

  Google Scholar 

• A. Caprara, D. Pisinger, and P. Toth, “Exact solution of quadratic knapsack problems,” INFORMS J. on Comput., vol. 11, no. 2, pp. 125–137, 1999.

  Google Scholar 

• C. De Simone, “The cut polytope and the boolean quadric polytope,” Discrete Mathematics, vol. 79, pp. 71–75, 1989.

  Google Scholar 

• M. Deza and M. Laurent, “Facets for the cut cone I,” Mathematical Programming, vol. 56, no. 2, pp. 121–160, 1992a.

  Google Scholar 

• M. Deza and M. Laurent, “Facets for the cut cone II,” Mathematical Programming, vol. 56, no. 2, pp. 161–188, 1992b.

  Google Scholar 

• C.E. Ferreira, A. Martin, C. De Souza, R. Weismantel, and L. Wolsey, “Formulations and valid inequalities for the node capacitated graph partitioning problem,” Mathematical Programming, vol. 74, no. 3, pp. 247–267, 1996.

  Google Scholar 

• G. Gallo, P.L. Hammer, and B. Simeone, “Quadratic knapsack problems,” Mathematical Programming Study, vol. 12, pp. 132–149, 1980.

  Google Scholar 

• M.X. Goemans and D.P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, pp. 1115–1145, 1995.

  Google Scholar 

• P.L. Hammer, E.L. Johnson, and U.N. Peled, “Facets of regular 0–1 polytopes,” Mathematical Programming, vol. 8, pp. 179–206, 1975.

  Google Scholar 

• P.L. Hammer and D.J. Rader, “Efficient methods for solving quadratic knapsack problems,” INFOR, vol. 35, no. 3, pp. 170–182, 1997.

  Google Scholar 

• C. Helmberg, S. Poljak, F. Rendl, and H. Wolkowicz, “Combining semidefinite and polyhedral relaxations for integer programs,” in Integer Programming and Combinatorial Optimization, E. Balas and J. Clausen (Eds.), Lecture Notes in Computer Science, vol. 920. Springer, 1995, pp. 124–134.

• C. Helmberg and F. Rendl, “Solving quadratic (0,1)-problems by semidefinite programs and cutting planes,” Mathematical Programming, vol. 82, pp. 291–315, 1998.

  Google Scholar 

• C. Helmberg and F. Rendl, “A spectral bundle method for semidefinite programming,” Preprint SC-97–37, ZIB Berlin, August 1997. Revised October 1997. SIAM J. Optim., vol. 10, no. 3, pp. 673–696.

  Google Scholar 

• C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, “An interior-point method for semidefinite programming,” SIAM Journal on Optimization, vol. 6, pp. 342–361, 1996a.

  Google Scholar 

• C. Helmberg, F. Rendl, and R. Weismantel, “Quadratic knapsack relaxations using cutting planes and semidefinite programming, in Integer Programming and Combinatorial Optimization, W.H. Cunningham, S.T. McCormick, and M. Queyranne (Eds.), Springer, June 1996b, pp. 175–189, vol. 1084, Lecture Notes in Computer Science,.

• C. Helmberg and R. Weismantel, “Cutting plane algorithms for semidefinite relaxations,” in Pardalos and Wolkowicz (1998), pp. 197–213.

• E. Johnson, A. Mehrotra, and G.L. Nemhauser, “Min-cut clustering,” Mathematical Programming, vol. 62, pp. 133–152, 1993.

  Google Scholar 

• D.J. Laughhunn, “Quadratic binary programming with application to capital-budgeting problems,” Operations Research, vol. 18, pp. 454–461, 1970.

  Google Scholar 

• L. Lovász, “Graph theory and integer programming,” Annals of Discrete Mathematics, vol. 4, pp. 141–158, 1979.

  Google Scholar 

• L. Lovász and A. Schrijver, “Cones of matrices and set functions and 0–1 optimization,” SIAM J. Optimization, vol. 1, no. 2, pp. 166–190, 1991.

  Google Scholar 

• J. Mitchell, P.M. Pardalos, and M.G.C. Resende, “Interior point methods for combinatorial optimization,” in Handbook of Combinatorial Optimization, vol. 1, D.-Z. Du and P.M. Pardalos (Eds.), Kluwer, 1998, pp. 189–298.

• S. Näher and C. Uhrig, “The LEDA User Manual Version R 3.3 beta,” Max-Planck-Institut für Informatik, Im Stadtwald, Building 46.1, D-66123 Saarbrücken, Germany. (http://www.mpi-sb.mpg.de/LEDA/leda.html)

• Y. Nesterov, “Semidefinite relaxation and nonconvex quadratic optimization,” Optimization Methods and Software, vol. 9, pp. 141–160, 1998.

  Google Scholar 

• M.W. Padberg, “The boolean quadric polytope,” Mathematical Programming, vol. 45, pp. 132–172, 1989.

  Google Scholar 

• P.M. Pardalos, Y. Ye, and C.-G. Han, “Algorithms for the solution of quadratic knapsack problems,” Linear Algebra and its Applications, vol. 152, pp. 69–91, 1991.

  Google Scholar 

• P.M. Pardalos and H. Wolkowicz, “Topics in semidefinite and interior-point methods,” Fields Institute Communications, Vol. 18, American Mathematical Society, 1998.

• H. Sherali and W. Adams, “A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,” SIAM J. Discr. Math., vol. 3, no. 3, pp. 411–430, 1990.

  Google Scholar 

• R. Weismantel, “On the 0/1 knapsack polytope,” Mathematical Programming, vol. 77, pp. 49–68, 1997.

  Google Scholar 

• L.A. Wolsey, “Faces of linear inequalities in 0–1 variables,” Mathematical Programming, vol. 8, pp. 165–178, 1975.

  Google Scholar 

Download references