A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
From MaRDI portal
Publication:5704137
DOI10.1287/moor.28.3.470.16391zbMath1082.90084OpenAlexW2077397558MaRDI QIDQ5704137
Publication date: 11 November 2005
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.28.3.470.16391
stable set polytopecut polytopelinear relaxationsemidefinite relaxationlift-and-project0--1 polytope
Related Items (only showing first 100 items - show all)
Narrow Proofs May Be Maximally Long ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sinkhorn Algorithm for Lifted Assignment Problems ⋮ Computing the Hausdorff Boundary Measure of Semialgebraic Sets ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts ⋮ Unnamed Item ⋮ Minotaur: a mixed-integer nonlinear optimization toolkit ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Copositive and semidefinite relaxations of the quadratic assignment problem ⋮ Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ Distributionally robust mixed integer linear programs: persistency models with applications ⋮ Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems ⋮ Interactive Proofs with Approximately Commuting Provers ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Duality for mixed-integer convex minimization ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ \(k\)-point semidefinite programming bounds for equiangular lines ⋮ Tree-width and the Sherali-Adams operator ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization ⋮ Theoretical challenges towards cutting-plane selection ⋮ A note on the stability number of an orthogonality graph ⋮ Partial Lagrangian relaxation for general quadratic programming ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ A bounded degree SOS hierarchy for polynomial optimization ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ Semidefinite representations for finite varieties ⋮ Strengthened semidefinite programming bounds for codes ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ A note on the Lasserre hierarchy for different formulations of the maximum independent set problem ⋮ Semidefinite bounds for the stability number of a graph via sums of squares of polynomials ⋮ DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips ⋮ Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality ⋮ A ``joint + marginal heuristic for 0/1 programs ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Atomic optimization. II. Multidimensional problems and polynomial matrix inequalities ⋮ Integrality gaps for colorful matchings ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Knapsack problem with probability constraints ⋮ Unnamed Item ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs ⋮ Minimal arc-sets spanning dicycles ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Proof Complexity Meets Algebra ⋮ The spherical constraint in Boolean quadratic programs ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ Extended formulations for convex envelopes ⋮ A guide to conic optimisation and its applications ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling ⋮ Approximate formulations for 0-1 knapsack sets ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Intermediate integer programming representations using value disjunctions ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Two new reformulation convexification based hierarchies for 0-1 MIPs ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ On the Lovász theta function and some variants ⋮ A new lift-and-project operator ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ A combinatorial approach to nonlocality and contextuality ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Unnamed Item ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Block-diagonal semidefinite programming hierarchies for 0/1 programming ⋮ Introduction to Semidefinite, Conic and Polynomial Optimization ⋮ Convex Relaxations and Integrality Gaps ⋮ Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion ⋮ Lift-and-project methods for set cover and knapsack ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Convexification techniques for linear complementarity constraints ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ New Tools for Graph Coloring ⋮ On semidefinite bounds for maximization of a non-convex quadratic objective over thel1unit ball ⋮ Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
This page was built for publication: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
