论文标题
夫人：基于半限定编程和ADMM的最大切割的平行精确求解器
MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM
论文作者
论文摘要
我们提出了女士，这是一种基于半限定的准精确求解器，用于最大切割，这是在给定图中找到最大重量的切割的问题。该算法使用分支和结合范式，将乘数的交替方向方法作为边界例程来解决基本的半决赛弛豫，从而通过超度不平等的子集得到了增强。新方法的好处是对二变量在不平等约束方面的计算昂贵更新规则较少。我们提供了算法的理论融合以及使用此方法的广泛计算实验，以表明我们的算法表现优于当前的最新方法。此外，通过结合串行算法的算法成分，我们基于MPI开发了有效的分布式并行求解器。
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.
