论文标题
使用整数编程和光谱聚类技术优化使用最小尺寸约束的连接组件分区
Optimizing Connected Components Graph Partitioning With Minimum Size Constraints Using Integer Programming and Spectral Clustering Techniques
论文作者
论文摘要
在这项工作中，考虑了固定数量的连接组件中的图形分区问题。给定边缘成本的无方向图，问题包括将一组节点划分为具有最小尺寸的固定数量的子集，其中每个子集都会引起一个连接的子图，并具有最小的边缘成本。该问题自然会在连通性至关重要的应用中涌现，例如社交网络，政治区域，运动队重新调整和能源分配中的集群检测。证明了混合整数编程配方以及各种有效的不平等现象并在计算测试中进行了测试。还提出了通过光谱聚类的辅助柱生成方法，该问题对于其他有效的不平等现象。最后，对几个模拟实例进行了测试，并讨论了计算结果。总体而言，通过光谱聚类增强的拟议的列生成技术为解决聚类和分区问题提供了有希望的方法。
In this work, a graph partitioning problem in a fixed number of connected components is considered. Given an undirected graph with costs on the edges, the problem consists of partitioning the set of nodes into a fixed number of subsets with minimum size, where each subset induces a connected subgraph with minimal edge cost. The problem naturally surges in applications where connectivity is essential, such as cluster detection in social networks, political districting, sports team realignment, and energy distribution. Mixed Integer Programming formulations together with a variety of valid inequalities are demonstrated and computationally tested. An assisted column generation approach by spectral clustering is also proposed for this problem with additional valid inequalities. Finally, the methods are tested for several simulated instances, and computational results are discussed. Overall, the proposed column generation technique enhanced by spectral clustering offers a promising approach to solve clustering and partitioning problems.
