  We investigate a new model for partitioning a set of items into groups
(clusters). The number of groups is given and the distances between items are
well defined. These distances may include weights. The sum of the distances
between all members of the same group is calculated for each group, and the
objective is to find the partition of the set of items that minimizes the sum
of these individual sums. Two problems are formulated and solved. In the first
problem the number of items in each group are given. For example, all groups
must have the same number of items. In the second problem there is no
restriction on the number of items in each group. We propose an optimal
algorithm for each of the two problems as well as a heuristic algorithm.
Problems with up to 100 items and 50 groups are tested. In the majority of
instances the optimal solution was found using IBM's CPLEX. The heuristic
approach, which is very fast, found all confirmed optimal solutions and equal
or better solutions when CPLEX was stopped after five hours. The problem with
given group sizes can also be formulated and solved as a quadratic assignment
problem.
