Lifting and separation procedures for the cut polytope

• 成果类型: Article
• 署名作者: Bonato, Thorsten; Juenger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni
• 署名单位: Ruprecht Karls University Heidelberg; University of Cologne; Consiglio Nazionale delle Ricerche (CNR)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0688-2
• 发表日期: 2014
• 页码: 351-378
• 关键词: bicycle wheel inequalities; exact ground-states; ising spin-glasses; Combinatorial Optimization; triangular elimination; bell inequalities; facets; algorithms

摘要

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems.