Details

Autor(en) / Beteiligte

• Koshimura, Miyuki
• Watanabe, Emi
• Sakurai, Yuko
• Yokoo, Makoto

Titel

Concise integer linear programming formulation for clique partitioning problems

Ist Teil von

• Constraints : an international journal, 2022-04, Vol.27 (1-2), p.99-115

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Quelle

SpringerLink

Beschreibungen/Notizen

• 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.