论文标题
最大切割，稳定集和着色的基于确切子图的SDP边界的计算研究
A Computational Study of Exact Subgraph Based SDP Bounds for Max-Cut, Stable Set and Coloring
论文作者
论文摘要
最近引入了“确切的子图”方法作为层次结构方案，以使几种NP-HARD图优化问题的半标准编程松弛越来越紧。解决这些放松是一项计算挑战，因为可能有大量的违反子图限制。我们为这些放松介绍了一个计算框架，旨在应对这些困难。我们建议部分拉格朗日双重双重，并利用其评估将其分解为几个独立子问题的事实。这打开了使用捆绑方法从非平滑优化的方法来最大程度地减少双重函数的方法。最后，在最大切割，稳定的集合和着色问题上进行了计算实验，显示了使用这种方法获得的界限的出色质量。
The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach.
