Computation with polynomial equations and inequalities arising in combinatorial optimization
From MaRDI portal
Publication:2897307
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.
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
Cites work
- scientific article; zbMATH DE number 5162350 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 108068 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1504686 (Why is no real title available?)
- scientific article; zbMATH DE number 2196288 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- A unified approach to computing real and complex zeros of zero-dimensional ideals
- An algebraist's view on border bases
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Another look at graph coloring via propositional satisfiability
- Characterizations of border bases
- Class of global minimum bounds of polynomial functions
- Complexity of Null- and Positivstellensatz proofs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Efficient algorithms for solving overdefined systems of multivariate polynomial equations
- Efficient decomposition of associative algebras over finite fields
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Numerical Polynomial Algebra
- Positive polynomials and sums of squares
- Random Graphs
- Recognizing graph theoretic properties with polynomial ideals
- Semidefinite Programming
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- Sharp Effective Nullstellensatz
- Solving polynomial equations. Foundations, algorithms, and applications
- Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
- Stable normal forms for polynomial system solving
- Stable sets and polynomials
- Sums of squares, moment matrices and optimization over polynomials
- The hardest constraint problems: A double phase transition
- Theta bodies for polynomial ideals
- Using Algebraic Geometry
Cited in
(10)- scientific article; zbMATH DE number 5823944 (Why is no real title available?)
- On the feasibility of semi-algebraic sets in Poisson regression
- A geometrical characterization of proportionally modular affine semigroups
- A Polyhedral Characterization of Border Bases
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- From combinatorial optimization to real algebraic geometry and back
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- scientific article; zbMATH DE number 1072400 (Why is no real title available?)
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Positive Plücker tree certificates for non-realizability
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)
