A new family of facet defining inequalities for the maximum edge-weighted clique problem

Published: 2015/08/31, Updated: 2017/08/08

0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches boolean quadric polytope, cutting planes, edge-weighted clique problem, facet defining inequalities, in- teger programming, separation algorithm Short URL: https://optimization-online.org/?p=13593

This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the maximum edge-weighted clique problem that use cutting planes.

Citation

Cahiers du GERAD, G-2015-71. Polytechnique Montreal - GERAD