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)
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
This page was built for publication: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
