论文标题
将项目划分为相互排他性的群体
Partitioning Items Into Mutually Exclusive Groups
论文作者
论文摘要
我们研究了将一组项目分组分组（集群）的新模型。给出了组的数量，并且项目之间的距离得到了很好的定义。这些距离可能包括重量。为每个组计算同一组成员之间的所有成员之间的距离之和，目的是找到最小化这些单个总和总和的项目集的分区。提出和解决两个问题。在第一个问题中，给出了每个组中的项目数。例如，所有组都必须具有相同数量的项目。在第二个问题中，对每个组中的项目数量没有限制。我们提出了两个问题中每种问题以及启发式算法的最佳算法。测试了多达100个项目和50组的问题。在大多数情况下，使用IBM的CPLEX发现了最佳解决方案。启发式方法非常快，当CPLEX在五个小时后停止时，发现了所有已确认的最佳解决方案和相等或更好的解决方案。给定的组大小的问题也可以作为二次分配问题制定和解决。
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.
