Concise integer linear programming formulation for clique partitioning problems
| العنوان: | Concise integer linear programming formulation for clique partitioning problems |
|---|---|
| المؤلفون: | Miyuki Koshimura, Emi Watanabe, Yuko Sakurai, Makoto Yokoo |
| المصدر: | Constraints. 27:99-115 |
| بيانات النشر: | Springer Science and Business Media LLC, 2022. |
| سنة النشر: | 2022 |
| مصطلحات موضوعية: | Computational Theory and Mathematics, Artificial Intelligence, Discrete Mathematics and Combinatorics, Software |
| الوصف: | 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, 1989). Recently, Miyauchi et al. (2018) 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. |
| تدمد: | 1572-9354 1383-7133 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::c9dc58ceaf696062b852bf229d3cf587 https://doi.org/10.1007/s10601-022-09326-z |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........c9dc58ceaf696062b852bf229d3cf587 |
| قاعدة البيانات: | OpenAIRE |
Find this article in full text from Springer Verlag. | تدمد: | 15729354 13837133 |
|---|