Quadratic knapsack relaxations using cutting planes and semidefinite programming

DOI10.1007/3-540-61310-2_14MaRDI QIDQ4645922zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Christoph Helmberg, Franz Rendl, Robert Weismantel

Publication date 11 January 2019

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61310-2_14

zbMATH Keywords

complete graphquadratic spacesemidefinite programmingvalid inequalityweight inequality

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• A semidefinite programming approach to the quadratic knapsack problem
• Combining semidefinite and polyhedral relaxations for integer programs
• scientific article; zbMATH DE number 1182577
• Linear programming relaxations of quadratically constrained quadratic programs
• A note on semidefinite relaxation for 0-1 quadratic knapsack problems

Cites work

• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• An Interior-Point Method for Semidefinite Programming
• Combining semidefinite and polyhedral relaxations for integer programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Min-cut clustering
• On the \(0/1\) knapsack polytope
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope

Cited in

(16)

• A semidefinite programming approach to the quadratic knapsack problem
• Efficient semidefinite branch-and-cut for MAP-MRF inference
• The quadratic 0-1 knapsack problem with series-parallel support
• SDP-based bounds for graph partition via extended ADMM
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• Upper bounds and exact algorithms for \(p\)-dispersion problems
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Linear programming relaxations of quadratically constrained quadratic programs
• Generating cutting planes for the semidefinite relaxation of quadratic programs
• Combining semidefinite and polyhedral relaxations for integer programs
• Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
• A Lagrangian relaxation approach to the edge-weighted clique problem
• Lagrangian heuristics for the quadratic knapsack problem
• Discrete location problems with push-pull objectives
• The quadratic knapsack problem -- a survey

This page was built for publication: Quadratic knapsack relaxations using cutting planes and semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645922)