  The moment-sum of squares hierarchy by Lasserre has become an established
technique for solving polynomial optimization problems. It provides a
monotonically increasing series of tight bounds, but has well-known scalability
limitations. For structured optimization problems, the term-sparsity SOS
(TSSOS) approach scales much better due to block-diagonal matrices, obtained by
completing the connected components of adjacency graphs. This block structure
can be exploited by semidefinite programming solvers, for which the overall
runtime then depends heavily on the size of the largest block. However, already
the first step of the TSSOS hierarchy may result in large diagonal blocks. We
suggest a new approach that refines TSSOS iterations using combinatorial
optimization and results in block-diagonal matrices with reduced maximum block
sizes. Numerical results on a benchmark library show the large potential for
computational speedup for unconstrained and constrained polynomial optimization
problems, while obtaining almost identical bounds in comparison to established
methods.
