Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/74935
Type: Artigo de periódico
Title: The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
Author: Macambira, EM
de Souza, CC
Abstract: 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.
Subject: edge-weighted cliques
polyhedral combinatorics
integer programming
branch-and-cut
Boolean Quadric Polytope
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/S0377-2217(99)00262-3
Date Issue: 2000
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000086582500011.pdf254.98 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.