Unlike linear models, systems of multivariate polynomial equations over the complex numbers or finite fields can be compactly used to model combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc.) if and only if a given system of polynomial equations has a solution. In the work of M. Laurent, J. Lasserre and P. Parrilo, Y.Nesterov, and others, continuous optimization problems which are modeled by zero-dimensional radical ideals have been shown to have a finite sequence of semidefinite programs that converge to an optimal solution. For yes/no combinatorial decision problems (e.g., is a graph 3-colorable?), we observed that Hilbert's Nullstellensatz gives a sequence of linear algebra problems that eventually determines feasibility. This has advantages as linear algebra is quite stable on computation and sparsity is well-understood.
In this talk, we present theoretical and experimental results on these sequences of large-scale, sparse, linear algebra relaxations to the combinatorial optimization problem. We show that the size of the smallest Nullstellensatz linear algebra system certifying that there is no stable set of size larger than the stability number of the graph grows as the stability number of the graph. We additionally describe ideas for optimizing the method, such as utilizing alternative forms of the Nullstellensatz, adding carefully-constructed polynomials to the system, branching and exploiting symmetry. Finally, in the case of 3-colorability, we use this method to successfully solve graph problem instances having thousands of nodes and tens of thousands of edges.
joint work with Jesus De Loera, Jon Lee, Peter Malkin and Shmuel Onn
Copyright. All Rights Reserved.