Quadratic knapsack relaxations using cutting planes and semidefinite programming

DOI10.1007/3-540-61310-2_14zbMath1415.90073OpenAlexW1509288136WikidataQ60395643 ScholiaQ60395643MaRDI QIDQ4645922

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

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

Related Items

SDP-based bounds for graph partition via extended ADMM, The quadratic knapsack problem -- a survey, Combining semidefinite and polyhedral relaxations for integer programs, Discrete location problems with push-pull objectives, A Lagrangian relaxation approach to the edge-weighted clique problem, Upper bounds and exact algorithms for \(p\)-dispersion problems, Lagrangian heuristics for the quadratic knapsack problem, Efficient semidefinite branch-and-cut for MAP-MRF inference, Parametric convex quadratic relaxation of the quadratic knapsack problem, The quadratic 0-1 knapsack problem with series-parallel support

Cites Work

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