Premium
An enhanced branch‐and‐bound algorithm for a partitioning problem
Author(s) -
Brusco Michael J.
Publication year - 2003
Publication title -
british journal of mathematical and statistical psychology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.157
H-Index - 51
eISSN - 2044-8317
pISSN - 0007-1102
DOI - 10.1348/000711003321645359
Subject(s) - branch and bound , partition (number theory) , upper and lower bounds , mathematics , block matrix , partition problem , algorithm , dynamic programming , mathematical optimization , branch and cut , set (abstract data type) , matrix (chemical analysis) , combinatorics , linear programming , computer science , mathematical analysis , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , composite material , programming language
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.