A branch-and-bound approach using polyhedral results for a clustering problem

This article describes a variation of the branch and bound method for solving a clustering problem stated as a partitioning problem on edge-weighted graphs. The key features of the approach are two. First, it employs the transformation of a subproblem according to some heuristic solution. For this, two clustering heuristics, constructive and iterative improvement, are adopted. Second, the lower bound computation is based on the use of the inequalities with zero right-hand side coefficient, each defining a facet of the polytope related to the transformed subproblem. A procedure is described for covering negative edges of the subproblem graph by cycles and paths inducing such inequalities. The objective function is modified each time by adding the left-hand side of the selected inequality to it. The lower bound is obtained by summing the weights of uncovered negative edges. The algorithm can be used for solving clustering problems in the area of qualitative data analysis. Computational results on both real and randomly generated clustering problems demonstrate the efficiency of the algorithm. In particular, all 10 real problems from the literature were solved in a total of less than 9 seconds on an IBM PC.