A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

DOI10.1137/130950173zbMath1332.90219arXiv1312.5972OpenAlexW2963362520MaRDI QIDQ2790405

Tunçel, Levent, Yu Hin (Gary) Au

Publication date: 4 March 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.5972

zbMATH Keywords

integer programmingsemidefinite programmingcombinatorial optimizationconvex relaxationslift-and-project methodsdesign and analysis of algorithms with discrete structures

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27) Set-valued operators (47H04) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (7)

Theoretical challenges towards cutting-plane selection ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Lift-and-project methods for set cover and knapsack ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smallest compact formulation for the permutahedron
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Expressing combinatorial optimization problems by linear programs
• Lift and project relaxations for the matching and related polytopes
• The stable set problem and the lift-and-project ranks of graphs
• Symmetry groups, semidefinite programs, and sums of squares
• Tighter representations for set partitioning problems
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• On a Representation of the Matching Polytope Via Semidefinite Liftings
• On the Matrix-Cut Rank of Polyhedra
• Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
• Approximation of the Stability Number of a Graph via Copositive Programming
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
• Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• The Matching Polytope has Exponential Extension Complexity
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Integrality gaps for Sherali-Adams relaxations
• Sherali-adams relaxations of the matching polytope
• CSP gaps and reductions in the lasserre hierarchy
• On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
• Paths, Trees, and Flowers
• Computation of the Lasserre Ranks of Some Polytopes
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• Linear vs. semidefinite extended formulations
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Sparsest cut on bounded treewidth graphs
• 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

This page was built for publication: A Comprehensive Analysis of Polyhedral Lift-and-Project Methods