Concise integer linear programming formulation for clique partitioning problems
Concise integer linear programming formulation for clique partitioning problems
复制标题
DOI：
10.1007/s10601-022-09326-z
复制
发表时间：
2022-04
期刊：
影响因子：
1.6
通讯作者：
Miyuki Koshimura;Emi Watanabe;Y. Sakurai;M. Yokoo
中科院分区：
文献类型：
--
作者：
Miyuki Koshimura;Emi Watanabe;Y. Sakurai;M. Yokoo
团划分问题（CPP）是对给定的边加权无向图进行最优划分，使得权值之和最大化。这个一般的图问题有着广泛的实际应用，包括相关聚类、成组技术、社区检测和联盟结构生成。虽然CPP是NP难的，但由于最近的线性规划（ILP）求解器的进步，我们可以通过将CPP公式化为ILP实例来解决相当大的问题实例。第一个ILP公式是由Grötschel和Wakabayashi介绍的（Mathematical Programming，45（1-3），59-96，）。最近，Miyauchi等人提出了一种更简洁的ILP公式，与以前引入的模型相比，它可以显着减少传递性约束。在本文中，我们介绍了一系列简洁的ILP公式，可以减少更多的传递性约束。我们从理论上评估减少量的基础上一个简单的模型，其中边缘符号（正/负）是独立选择的。我们表明，减少可以高达50%（依赖于负边缘的比率）和实验评估的减少量和我们提出的配方使用各种图形数据集的性能。实验评估表明，减少可以超过50%（边缘符号可以相关），我们的配方优于现有的最先进的配方，无论是在内存使用和计算时间方面的大多数问题的情况。
A Clique Partitioning Problem (CPP) finds an optimal partition of a given edge-weighted undirected graph, such that the sum of the weights is maximized. This general graph problem has a wide range of real-world applications, including correlation clustering, group technology, community detection, and coalition structure generation. Although a CPP is NP-hard, due to the recent advance of Integer Linear Programming (ILP) solvers, we can solve reasonably large problem instances by formulating a CPP as an ILP instance. The first ILP formulation was introduced by Grötschel and Wakabayashi (Mathematical Programming, 45(1-3), 59–96, ). Recently, Miyauchi et al. proposed a more concise ILP formulation that can significantly reduce transitivity constraints as compared to previously introduced models. In this paper, we introduce a series of concise ILP formulations that can reduce even more transitivity constraints. We theoretically evaluate the amount of reduction based on a simple model in which edge signs (positive/negative) are chosen independently. We show that the reduction can be up to 50% (dependent of the ratio of negative edges) and experimentally evaluate the amount of reduction and the performance of our proposed formulation using a variety of graph data sets. Experimental evaluations show that the reduction can exceed 50% (where edge signs can be correlated), and our formulation outperforms the existing state-of-the-art formulations both in terms of memory usage and computational time for most problem instances.