The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations ?
Let Kn=(V,E) be the complete undirected graph with weights ce associated to the edges in E. We consider the problem of finding the subclique C=(U,F) of Kn such that the sum of the weights of the edges in F is maximized and |U|?b, for some b?[1,,n]. This problem is called the Maximum Edge-Weighted Clique Problem (MEWCP) and is NP-hard. In this paper we investigate the facial structure of the polytope associated to the MEWCP introducing new classes of facet defining inequalities. Computational experiments with a branch-and-cut algorithm are reported confirming the strength of these inequalities. All instances with up to 48 nodes could be solved without entering into the branching phase. Moreover, we show that some of these new inequalities also define facets of the Boolean Quadric Polytope and generalize many of the previously known inequalities for this well-studied polytope.
edge-weighted cliques branch-and-cut boolean quadric polytope polyhedral combinatorics integer programming