Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
From MaRDI portal
Publication:1662113
DOI10.1016/j.disopt.2017.10.001zbMath1506.90213arXiv1608.07647OpenAlexW2963134868MaRDI QIDQ1662113
Yu Hin (Gary) Au, Tunçel, Levent
Publication date: 17 August 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.07647
integer programmingsemidefinite programmingcombinatorial optimizationconvex relaxationsintegrality gaplift-and-project methods
Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items
Breaking symmetries to rescue sum of squares in the case of makespan scheduling, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cutting planes from extended LP formulations
- On cutting-plane proofs in combinatorial optimization
- Disjunctive programming: Properties of the convex hull of feasible points
- A new lift-and-project operator
- Design and verify: a new scheme for generating cutting-planes
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- On the Matrix-Cut Rank of Polyhedra
- A Comprehensive Analysis of Polyhedral Lift-and-Project Methods
- Theta Bodies for Polynomial Ideals
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- On the Rank of Cutting-Plane Proof Systems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Computation of the Lasserre Ranks of Some Polytopes
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
