Combining semidefinite and polyhedral relaxations for integer programs

DOI10.1007/3-540-59408-6_46zbMath1498.90138OpenAlexW1527552358MaRDI QIDQ5101410

Henry Wolkowicz, Svatopluk Poljak, Franz Rendl, Christoph Helmberg

Publication date: 30 August 2022

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

Full work available at URL: https://doi.org/10.1007/3-540-59408-6_46

zbMATH Keywords

quadratic knapsack problemconstrained \(0-1\) quadratic programming

Mathematics Subject Classification ID

Integer programming (90C10) Interior-point methods (90C51) Combinatorial optimization (90C27)

Related Items

On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Semidefinite programming and combinatorial optimization, Efficient semidefinite branch-and-cut for MAP-MRF inference, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

Cites Work

• Experiments in quadratic 0-1 programming
• Laplacian eigenvalues and the maximum cut problem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• 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
• On the Shannon capacity of a graph
• Quadratic knapsack relaxations using cutting planes and semidefinite programming
• An Interior-Point Method for Semidefinite Programming
• Unnamed Item