Computation with polynomial equations and inequalities arising in combinatorial optimization
From MaRDI portal
Publication:2897307
DOI10.1007/978-1-4614-1927-3_16zbMATH Open1242.90191arXiv0909.0808OpenAlexW1828856524MaRDI QIDQ2897307FDOQ2897307
Authors: Jesús A. De Loera, Peter N. Malkin, Pablo A. Parrilo 
Publication date: 10 July 2012
Published in: Mixed Integer Nonlinear Programming (Search for Journal in Brave)
Abstract: The purpose of this note is to survey a methodology to solve systems of polynomial equations and inequalities. The techniques we discuss use the algebra of multivariate polynomials with coefficients over a field to create large-scale linear algebra or semidefinite programming relaxations of many kinds of feasibility or optimization questions. We are particularly interested in problems arising in combinatorial optimization.
Full work available at URL: https://arxiv.org/abs/0909.0808
Recommendations
- Optimization over polynomials: selected topics
- Sums of squares, moment matrices and optimization over polynomials
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Semidefinite programming in combinatorial and polynomial optimization
- Semidefinite representations for finite varieties
combinatorial optimizationsemidefinite programmingpositivstellensatzreal algebrasemi-algebraic setsstable setsgraph colorabilityMax-cutnullstellensatzlarge-scale linear algebrapolynomial equations and inequalities
Cites Work
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Title not available (Why is that?)
- Random Graphs
- Semidefinite Programming
- Using Algebraic Geometry
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Title not available (Why is that?)
- GloptiPoly
- Stable sets and polynomials
- Semidefinite programming relaxations for semialgebraic problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Sums of squares, moment matrices and optimization over polynomials
- Class of global minimum bounds of polynomial functions
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Title not available (Why is that?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Semidefinite representations for finite varieties
- Efficient algorithms for solving overdefined systems of multivariate polynomial equations
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Another look at graph coloring via propositional satisfiability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Numerical Polynomial Algebra
- Positive polynomials and sums of squares
- The hardest constraint problems: A double phase transition
- Title not available (Why is that?)
- Sharp Effective Nullstellensatz
- Solving polynomial equations. Foundations, algorithms, and applications
- Characterizations of border bases
- Stable normal forms for polynomial system solving
- An algebraist's view on border bases
- Theta bodies for polynomial ideals
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Title not available (Why is that?)
- Efficient decomposition of associative algebras over finite fields
- Title not available (Why is that?)
- Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
- A unified approach to computing real and complex zeros of zero-dimensional ideals
- Recognizing graph theoretic properties with polynomial ideals
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Complexity of Null- and Positivstellensatz proofs
Cited In (10)
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- A geometrical characterization of proportionally modular affine semigroups
- From combinatorial optimization to real algebraic geometry and back
- On the feasibility of semi-algebraic sets in Poisson regression
- Positive Plücker tree certificates for non-realizability
- A Polyhedral Characterization of Border Bases
- Title not available (Why is that?)
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Title not available (Why is that?)
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
Uses Software
This page was built for publication: Computation with polynomial equations and inequalities arising in combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897307)
