Improving upper bounds for the clique number by non-valid inequalities

• 成果类型: Article
• 署名作者: Locatelli, Marco
• 署名单位: University of Parma
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0771-3
• 发表日期: 2015
• 页码: 511-525
• 关键词: quadratic optimization problems; maximum clique; positive matrices; stability number; LOCAL SEARCH; graph; relaxations; cones

摘要

The Lovasz and Lovasz-Schrijver bounds are well known upper bounds for the clique number of a graph, based on the solution of semidefinite programming problems. Both bounds can be seen as obtained through a relaxation of a completely positive formulation of the maximum clique problem. In this paper we propose to improve these bounds by adding inequalities based on independent sets, which may be non-valid, in the sense that they may be violated by optimal solutions of the completely positive formulation. Some computational experiments have been performed over different classes of graphs and the results are promising.