Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization

Jesús A. De Loera, Peter N. Malkin, Pablo A. Parrilo2011 · DOI · arXiv · OpenAlex

Abstract

This survey explores the application of algebraic geometry to combinatorial optimization, specifically translating discrete problems into systems of polynomial equations and inequalities. By utilizing Hilbert’s Nullstellensatz and Stengle’s Positivstellensatz, the authors develop hierarchies of linear and semidefinite programming relaxations to solve or certify the infeasibility of NP-hard problems.

Introduction

Combinatorial optimization often deals with discrete feasibility questions or finding the optimal configuration among an astronomically large set of possibilities, such as graph coloring or max-cut problems. These problems are typically NP-hard, making them computationally intractable as they scale. The central challenge lies in the discrete nature of these problems, whereas the most powerful optimization tools, like Linear Programming (LP), operate best in continuous spaces.

This paper addresses this gap by modeling discrete constraints as continuous polynomial equations. For instance, a binary choice can be represented by the equation $x_i^2 - x_i = 0$. Once modeled this way, the authors apply algebraic theorems to extract meaningful bounds or formal proofs of infeasibility.

Algebraic Frameworks and Methodology

The authors categorize their approach into two main algebraic frameworks based on whether the system involves pure equations or includes inequalities. This classification is summarized in Table 1, which relates these advanced algebraic tools to classical linear algebra and programming.

Table 1: Classification of certificates and optimization methods based on degree and field.

1. Systems of Equations: The Nullstellensatz Approach

For systems of equations, the authors utilize Hilbert’s Nullstellensatz, which states that a system is infeasible if and only if the constant 1 can be expressed as a combination of the system's polynomials.

  • NulLA Algorithm: This reduces the feasibility problem to solving a sequence of increasingly large systems of linear equations.
  • FPNulLA (Fixed-Point NulLA): An improved version that incorporates "redundant" equations—logically implied by the original set—to tighten the relaxation. This often allows the solver to find a certificate at a lower polynomial degree, significantly speeding up computation.

2. Systems with Inequalities: The Positivstellensatz Approach

When inequalities are present, the authors turn to Stengle’s Positivstellensatz and Sum of Squares (SOS) relaxations.

  • SOS Relaxations: A system is proven infeasible if -1 can be expressed as a sum of squares plus a combination of the constraints. Finding these SOS certificates is equivalent to solving a Semidefinite Program (SDP), a type of convex optimization more powerful than standard LP.
  • Theta Bodies: These are convex relaxations of the solution set. Notably, the first level of this hierarchy for the "stable set" problem corresponds to the famous Lovász theta body.

Experimental Evaluation and Key Results

The paper evaluates these algorithms primarily using random graphs ($G(n, p)$ model) and 3-coloring benchmarks. Testing the NulLA and FPNulLA algorithms on 1,000 random graphs with 100 vertices revealed several key insights:

  • Phase Transitions: There is a specific edge density where problems shift from being easily provable as feasible to easily provable as infeasible. The most computationally difficult problems reside at this boundary.
  • Structural Characterization: The authors proved that for non-3-colorable graphs containing specific structures like odd-wheels or 4-cliques, the NulLA degree is exactly one, allowing for highly efficient infeasibility proofs.
  • Solution Recovery: Beyond proving infeasibility, the paper describes using eigenvalue and eigenvector methods on "multiplication operators" to extract actual discrete solutions from the continuous relaxations.

Limitations and Future Directions

Despite the power of these algebraic tools, several challenges remain:

  • Degree Explosion: The "Nullstellensatz degree" required for a certificate can be exponentially high in the worst case, an unavoidable consequence of NP-hardness.
  • Numerical Sensitivity: As the degree of SOS/SDP relaxations increases, the size of the matrices grows rapidly, leading to memory constraints and numerical stability issues.
  • Feasibility vs. Infeasibility: Current methods are generally more robust at providing certificates of infeasibility than at finding feasible solutions for very large, complex systems. Future research aims to refine the recovery phase to handle larger-scale problems more reliably.

Summary updated

BibTeX
@inproceedings{loera2011computation,
  author = {Jesús A. De Loera and Peter N. Malkin and Pablo A. Parrilo},
  title = {{Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization}},
  booktitle = {˜The},
  year = {2011},
  doi = {10.1007/978-1-4614-1927-3\_16},
}

Loading related content...

Figure