Artículos de revistas
The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
Registro en:
European Journal Of Operational Research. Elsevier Science Bv, v. 123, n. 2, n. 346, n. 371, 2000.
0377-2217
WOS:000086582500011
10.1016/S0377-2217(99)00262-3
Autor
Macambira, EM
de Souza, CC
Institución
Resumen
Let k(n) = (V,E) be the complete undirected graph with weights c(e) associated to the edges in E. We consider the problem of finding the subclique C = (U, F) of K-n such that the sum of the weights of the edges in F is maximized and \U\ less than or equal to b, for some b is an element of [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. (C) 2000 Elsevier Science B.V. All rights reserved. 123 2 346 371