An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
From MaRDI portal
Publication:2784435
DOI10.1137/S1052623400380079zbMath1007.90046OpenAlexW1997672673MaRDI QIDQ2784435
Publication date: 23 April 2002
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s1052623400380079
Semidefinite programming (90C22) Nonlinear programming (90C30) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items (63)
SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems ⋮ Products of positive forms, linear matrix inequalities, and Hilbert 17th problem for ternary forms ⋮ Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ \(k\)-point semidefinite programming bounds for equiangular lines ⋮ Sums of squares on the hypercube ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Convex sets with semidefinite representation ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ A polynomial approach for optimal control of switched nonlinear systems ⋮ A linear programming reformulation of the standard quadratic optimization problem ⋮ A ``joint + marginal heuristic for 0/1 programs ⋮ Partial Lasserre relaxation for sparse Max-Cut ⋮ Integrality gaps for colorful matchings ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Optimal Learning in Linear Regression with Combinatorial Feature Selection ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming ⋮ Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization ⋮ An exact algorithm for linear integer programming problems with distributionally robust chance constraints ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts ⋮ Optimal control of switching topology networks ⋮ Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ Stability and Bifurcations in a Model of Bacteria Immunity with Quorum Sensing ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ Exploiting equalities in polynomial programming ⋮ Efficiency improvement in an \(n\)D systems approach to polynomial optimization ⋮ A multilevel analysis of the Lasserre hierarchy ⋮ The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ On semidefinite least squares and minimal unsatisfiability ⋮ Cones of multipowers and combinatorial optimization problems ⋮ A polynomial approach for stability analysis of switched systems ⋮ A combinatorial approach to nonlocality and contextuality ⋮ Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems ⋮ The domain of attraction for the endemic equilibrium of an SIRS epidemic model ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ Uniform stabilization of discrete-time switched and Markovian jump linear systems ⋮ Robust global optimization with polynomials ⋮ An improved semidefinite programming relaxation for the satisfiability problem ⋮ Dynamic modeling and analysis of the email virus propagation ⋮ Sparsity in sums of squares of polynomials ⋮ Approximate graph colouring and the hollow shadow ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ A semidefinite programming approach to the generalized problem of moments ⋮ Block-diagonal semidefinite programming hierarchies for 0/1 programming ⋮ Convex Hulls of Algebraic Sets ⋮ Computational Approaches to Max-Cut ⋮ Lift-and-project methods for set cover and knapsack ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ Moment methods in energy minimization: New bounds for Riesz minimal energy problems ⋮ Unnamed Item ⋮ The theta number of simplicial complexes ⋮ New product introduction against a predator: A bilevel mixed-integer programming approach ⋮ Completely positive reformulations for polynomial optimization ⋮ The density of sets avoiding distance 1 in Euclidean space ⋮ Better approximation algorithms for influence maximization in online social networks ⋮ An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems ⋮ A dynamic inequality generation scheme for polynomial programming
This page was built for publication: An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
