An application of the Lovasz-Schrijver M(K, K) operator to the stable set problem

• 成果类型: Article
• 署名作者: Giandomenico, Monia; Letchford, Adam N.; Rossi, Fabrizio; Smriglio, Stefano
• 署名单位: University of L'Aquila; Lancaster University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0219-8
• 发表日期: 2009
• 页码: 381-401
• 关键词: branch-and-cut; bound algorithm; max-cut; relaxations; graphs; clique; PROGRAMS; packing

摘要

Although the lift-and-project operators of Lovasz and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.