An explicit exact SDP relaxation for nonlinear 0-1 programs

Recommendations

An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
Semidefinite programming relaxation for nonconvex quadratic programs
The equivalence of semidefinite relaxations of polynomial 0-1 and 1 programs via scaling
Best ellipsoidal relaxation to solve a nonconvex problem.
New SDP relaxations for unconstrained 0-1 polynomial programming problems

Cited in

(98)

Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
Tight size-degree bounds for sums-of-squares proofs
Minimal arc-sets spanning dicycles
Two new reformulation convexification based hierarchies for 0-1 MIPs
Binary quadratic optimization problems that are difficult to solve by conic relaxations
A new lift-and-project operator
Geometric proofs for convex hull defining formulations
A computational study on the quadratic knapsack problem with multiple constraints
Lift-and-project ranks and antiblocker duality
Exact SDP relaxations for classes of nonlinear semidefinite programming problems
Ensemble clustering using semidefinite programming with applications
Lift \& project systems performing on the partial-vertex-cover polytope
Penalized semidefinite programming for quadratically-constrained quadratic optimization
Polyhedral approximations of the semidefinite cone and their application
Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
Exact dual bounds for some nonconvex minimax quadratic optimization problems
Matroid optimization problems with monotone monomials in the objective
Between steps: intermediate relaxations between big-M and convex hull formulations
Lasserre integrality gaps for graph spanners and related problems
Fair colorful \(k\)-center clustering
Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
Strengthening convex relaxations of 0/1-sets using Boolean formulas
Sparse learning via Boolean relaxations
Tree-width and the Sherali-Adams operator
Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
Polyhedra related to integer-convex polynomial systems
Approximate fixed-rank closures of covering problems
Copositivity cuts for improving SDP bounds on the clique number
An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
A comprehensive analysis of polyhedral lift-and-project methods
Convex relaxations and integrality gaps
Invariant Semidefinite Programs
Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
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
Integrality gaps for strengthened linear relaxations of capacitated facility location
New tools for graph coloring
A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
New SDP relaxations for unconstrained 0-1 polynomial programming problems
Lehman's theorem and the directed Steiner tree problem
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
Communication lower bounds via critical block sensitivity
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
A nearly tight sum-of-squares lower bound for the planted clique problem
Fair colorful k-center clustering
Mathematical programming models and exact algorithms
Finite convergence of sum-of-squares hierarchies for the stability number of a graph
Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
Sum-of-squares bounds via Boolean function analysis
A unified approach to mixed-integer optimization problems with logical constraints
A notion of total dual integrality for convex, semidefinite, and extended formulations
No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
Narrow proofs may be maximally long
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
Approximating CSPs with global cardinality constraints using SDP hierarchies
Sum-of-squares hierarchies for binary polynomial optimization
Sum-of-squares hierarchies for binary polynomial optimization
Evaluating approximations of the semidefinite cone with trace normalized distance
DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips
Bootstrap, Markov chain Monte Carlo, and LP/SDP hierarchy for the lattice Ising model
A knapsack intersection hierarchy
An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
Perfect matching in random graphs is as hard as Tseitin
Proof complexity and the binary encoding of combinatorial principles
Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
On different versions of the exact subgraph hierarchy for the stable set problem
Partial reformulation-linearization based optimization models for the Golomb ruler problem
On connections between association schemes and analyses of polyhedral and positive semidefinite lift-and-project relaxations
The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
The Kikuchi hierarchy and tensor PCA
On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy
Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SPD operator
Sum-of-squares relaxations for information theory and variational inference
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
Application of the level-2 quantum Lasserre hierarchy in quantum approximation algorithms
Convergence rates of sum-of-squares hierarchies for polynomial semidefinite programs
On the bit size of sum-of-squares proofs for symmetric formulations
On the degree automatability of sum-of-squares proofs
P-split formulations: a class of intermediate formulations between big-M and convex hull for disjunctive constraints
Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity
An improved SDP rounding approximation algorithm for the max hypergraph bisection
Minotaur: a mixed-integer nonlinear optimization toolkit
Copositive programming motivated bounds on the stability and the chromatic numbers
Conic mixed-integer rounding cuts
Semidefinite representations for finite varieties
Strengthened semidefinite programming bounds for codes
Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
The equivalence of semidefinite relaxations of polynomial 0-1 and 1 programs via scaling
Approximate formulations for 0-1 knapsack sets
Valid inequalities for mixed integer linear programs

This page was built for publication: An explicit exact SDP relaxation for nonlinear 0-1 programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4537750)