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
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, Matroid optimization problems with monotone monomials in the objective, A sublevel moment-SOS hierarchy for polynomial optimization, The theta number of simplicial complexes, Sum-of-Squares Rank Upper Bounds for Matching Problems, Cuts for mixed 0-1 conic programming, Sherali-Adams relaxations of graph isomorphism polytopes, Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs, Polyhedra related to integer-convex polynomial systems, Approximate fixed-rank closures of covering problems, Superlinear Integrality Gaps for the Minimum Majority Problem, Sparse learning via Boolean relaxations, Completely positive reformulations for polynomial optimization, The density of sets avoiding distance 1 in Euclidean space, Lasserre integrality gaps for graph spanners and related problems, A dynamic inequality generation scheme for polynomial programming
