A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring

• 成果类型: Article
• 署名作者: Gaar, Elisabeth; Rendl, Franz
• 署名单位: University of Klagenfurt
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01512-2
• 发表日期: 2020
• 页码: 283-308
• 关键词: bundle methods; maximum cut; semidefinite; relaxations; APPROXIMATE; hierarchy; 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.