The maximum dispersion problem
The maximum dispersion problem
复制标题
DOI：
10.1016/j.omega.2012.09.005
复制
发表时间：
2013-08
影响因子：
6.9
通讯作者：
E. Fernández;J. Kalcsics;S. Nickel
中科院分区：
文献类型：
--
作者：
E. Fernández;J. Kalcsics;S. Nickel
在最大离散问题中，一组给定的对象必须被划分为若干组。每个对象具有非负权重，并且每个组具有目标权重，该目标权重对于每个组可能不同。除了满足每个组的目标权重外，分配给同一组的所有对象应尽可能分散，以实现对象对之间的距离测量。这个问题的潜在应用来自于不同的领域，如创建研究小组或废物收集系统的设计问题。我们开发和比较两种不同的（混合）整数线性规划公式的问题。我们还研究了一个特定的放松，使我们能够得到严格的界限，提高配方的有效性。由此，我们通过在辅助图中找到具有最小直径的给定大小的子集来获得上界。根据松弛的最优解与一系列辅助图的色数之间的关系，导出了一个下界。最后，我们提出了一个精确的解决方案的最大色散问题，并提出了广泛的计算实验，以评估其效率。
In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.