# MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM

arXiv: https://arxiv.org/abs/2010.07839 · HTML: https://mlsanity.com/paper/2010.07839/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2020.

## Built on by (most cited first, 3 of 3)

- [Monte Carlo Policy Gradient Method for Binary Optimization](https://mlsanity.com/paper/2307.00783/) (2023)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks](https://mlsanity.com/paper/2605.07113/) (2026)

## Abstract (arXiv)

We present MADAM, a parallel semidefinite based exact solver for Max-Cut, a problem of finding the cut with maximum weight in a given graph. The algorithm uses branch and bound paradigm that applies alternating direction method of multipliers as the bounding routine to solve the basic semidefinite relaxation strengthened by a subset of hypermetric inequalities. The benefit of the new approach is less computationally expensive update rule for the dual variable with respect to the inequality constraints. We provide theoretical convergence of the algorithm, as well as extensive computational experiments with this method, to show that our algorithm outperformes current state-of-the-art approaches. Furthermore, by combining algorithmic ingredients from the serial algorithm we develop an efficient distributed parallel solver based on MPI.