We present an exact solver for the Max-Cut problem, exploiting recent advances in solving diagonally constrained semidefinite programs. The solver uses a branch-and-cut paradigm and strengthens the basic semidefinite programming relaxation by adding clique inequalities. The cutting planes are handled via Lagrangian relaxation and the inner semidefinite programming problem is approximately solved by the Mixing method, an efficient first-order and low-rank algorithm.

We propose a new branching rule that exploits both primal and dual information, resulting in fewer explored subproblems. Moreover, we reduce the number of cutting-plane iterations by effectively handing down the cuts in the search tree. We demonstrate our results against state-of-the-art algorithms by means of an in-depth study on numerous dense Max-Cut instances. It turns out that our solver is not only faster than other existing approaches, but also scales better for larger instances.

BiqCrunch is a branch-and-bound solver using semidefinite optimization to compute high-quality bounds for combinatorial optimization problems that can be modeled as binary quadratic problems, such as MaxCut, Max-k-Cluster, Maximum-Independent-Set, Exact Quadratic Knapsack, and the Quadratic Assignment Problem.

BiqCrunch does not use an interior-point method for computing its bounds. Instead, an eigenvalue computation and a gradient-based method are used to compute the semidefinite bounds.

We will discuss our work on using the ALPS framework to run BiqCrunch with MPI on the HPC computer cluster at Northern Illinois University, and present numerical results.

Sidorenko’s conjecture can be formulated as "Let H be a bipartite graph, and ρ ∈ [0, 1]. Of all the graphs with edge density ρ, the graph(-limit) obtained by picking edges uniformly at random minimizes the homomorphism density of H."

This conjecture, first formulated in 1991 by Sidorenko, has received considerable attention over the last decades, and yet remains open in the general case. It was shown recently [Blekherman, Raymond, Singh, Thomas, 2020] that sums-of-squares in Razborov’s flag algebra are not strong enough to prove even small, known cases of the conjecture. To circumvent this, we introduce a novel kind of (Lie-)derivation of flags. Due to their combinatoric nature, we can use them to systematically gain knowledge on global minimizers of problems in extremal graph theory. We combine them with the flag algebra method to find new proofs for various cases of Sidorenko’s conjecture.

A famous problem in extremal graph theory is Sidorenko's conjecture which states that for a fixed bipartite graph H, the density of H in a graph of a given edge density is asymptotically minimized by a random graph. In this talk, we discuss some strengths and limitations of the sums of squares method to prove this conjecture for various families of bipartite graphs. We also present some computational results.