A branch and bound method for the aggregation of symmetric relations
Résumé
We consider the problem of the aggregation of symmetric
relations into a median equivalence relation, with in particular two spe-
cial cases: the one for which the symmetric relations are equivalence
relations (Régnier's problem), and the one of the approximation of one
symmetric relation by an equivalence relation (Zahn's problem). These
problems arise for instance from the field of classication or clustering,
when one wants to gather objects in such a way that the objects of any
cluster can be considered as similar, while the objects of different clusters
can be considered as dissimilar. We first state this problem as a clique
partitioning problem in graph theory. As this problem is NP-hard, we
then design a branch and bound algorithm to solve this problem, based
on a Lagrangean relaxation method for the evaluation function and on
noising methods for the initial bound.