Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition

• 成果类型: Article; Proceedings Paper
• 署名作者: Fischer, I; Gruber, G; Rendl, F; Sotirov, R
• 署名单位: University of Vienna; University of Klagenfurt; University of Melbourne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0661-9
• 发表日期: 2006
• 页码: 451-469
• 关键词: interior-point methods; volume algorithm; maximum cut

摘要

We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods.