@techreport{TR-IC-97-14,
number = {IC-97-14},
author = {Macambira, Elder M. and de Souza, Cid C.},
title = {The {Edge}-{Weighted} {Clique} {Problem}: {Valid} Inequalities, Facets and Polyhedral Computations},
month = {October},
year = {1997},
institution = {Institute of Computing, University of Campinas},
note = {In English, 25 pages.
\par\selectlanguage{english}\textbf{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| \leq b$,
for some $b \in [1,\ldots,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 and introduce new classes of facets for
this polytope. 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 previously known
inequalities for this polytope.
}
}