  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.
