An enhanced branch-and-bound algorithm for a partitioning problem.
This paper focuses on the problem of developing a partition of n objects based on the information in a symmetric, non-negative dissimilarity matrix. The goal is to partition the objects into a set of non-overlapping subsets with the objective of minimizing the sum of the within-subset dissimilarities. Optimal solutions to this problem can be obtained using dynamic programming, branch-and-bound and other mathematical programming methods. An improved branch-and-bound algorithm is shown to be particularly efficient. The improvements include better upper bounds that are obtained via a fast exchange algorithm and, more importantly, sharper lower bounds obtained through sequential solution of submatrices. A modified version of the branch-and-bound algorithm for minimizing the diameter of a partition is also presented. Computational results for both synthetic and empirical dissimilarity matrices reveal the effectiveness of the branch-and-bound methodology.
Brusco
Michael J
MJ
Department of Marketing, Florida State University, Tallahassee, FL 32306, USA. mbrusco@cob.fsu.edu
D000465:Algorithms; D006801:Humans; D008960:Models, Psychological; D011584:Psychology / Q000379:methods* / Q000706:statistics & numerical data*