Gaar Elisabeth, Rendl Franz
Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstr. 65-67, 9020 Klagenfurt, Austria.
Math Program. 2020;183(1):283-308. doi: 10.1007/s10107-020-01512-2. Epub 2020 May 25.
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.
“精确子图”方法最近被引入作为一种分层方案，用于获得几个NP难图优化问题越来越紧的半定规划松弛。由于可能存在大量违反子图约束的情况，求解这些松弛是一个计算挑战。我们为这些松弛引入了一个计算框架，旨在应对这些困难。我们提出了一个部分拉格朗日对偶，并利用其评估可分解为几个独立子问题这一事实。这为使用非光滑优化中的束方法来最小化对偶函数开辟了道路。最后，关于最大割、稳定集和着色问题的计算实验表明了用这种方法获得的界的优良质量。
