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

semidefinite programmingcomplete graphvalid inequalityquadratic spaceweight inequality

Mathematics Subject Classification ID

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

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)

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

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)