joint work with Renata Sotirov, Juan Vera
For a given graph with n vertices, we look for the largest induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We propose several new SDP upper bounds for this problem. The matrix size in the basic SDP relaxations grows with k. To avoid this growth, we use the invariance of the problem under the color permutations. As a result, the matrix size reduces to order (n+1), independently of k or the graph considered. Numerical experiments show that our bounds are tighter than the existing SDP and IP-based bounds for about a half of tested graphs.
A novel convexification strategy based on relaxing monomial relationships is presented. We embed both currently popular strategies, general approaches rooted in nonlinear programming and approaches based on sum-of-squares or moment relaxations, into a unified framework. Within this framework we are able to trade off the quality of relaxation against computational expenses. Our computational experiments show that a combination with a prototype cutting-plane algorithm gives very encouraging results.
joint work with Adam Kurpisz
We compare four key hierarchies for solving Constrained Polynomial Optimization Problems (CPOP): Sum of Squares (SOS), Sum of Diagonally Dominant (SDSOS), Sum of Nonnegative Circuits (SONC), and the Sherali Adams (SA) hierarchies. We prove a collection of dependencies among these hierarchies. In particular, we show on the Boolean hypercube that Schmüdgen-like versions SDSOS*, SONC*, and SA* of the hierarchies are polynomially equivalent. Moreover, we show that SA* is contained in any Schmüdgen-like hierarchy that provides a O(n) degree bound.