Volume 26, No 3, 2019, P. 60-87

UDC 519.1+519.8
R. Yu. Simanchev, I. V. Urazova, and Yu. A. Kochetov
The branch and cut method for the clique partitioning problem

Abstract:
A numerical study is carried out of the branch and cut method adapted for solving the clique partitioning problem (CPP). The problem is to find a family of pairwise disjoint cliques with minimum total weight in a complete edge-weighted graph. The two particular cases of the CPP are considered: The first is known as the aggregating binary relations problem (ABRP), and the second is the graph approximation problem (GAP). For the previously known class of facet inequalities of the polytope of the problem, the cutting-plane algorithm is developed. This algorithm includes the two new basic elements: finding a solution with given guaranteed accuracy and a local search procedure to solve the problem of inequality identification. The proposed cutting-plane algorithm is used to construct lower bounds in the branch and cut method. Some special heuristics are used to search upper bounds for the exact solution. We perform a numerical experiment on randomly generated graphs. Our method makes it possible to find an optimal solution for the previously studied cases of the ABRP and for new problems of large dimension. The GAP turns out to be a more complicated case of the CPP in the computational aspect. Moreover, some simple and difficult classes of the GAPs are identified for our algorithm.
Tab. 5, illustr. 1, bibliogr. 32.

Keywords: branch and cut, facet inequality, local search.

DOI: 10.33048/daio.2019.26.661

Ruslan Yu. Simanchev ^1,2
Inna V. Urazova ²
Yury A. Kochetov ³
1. Omsk Scientific Center SB RAN,
15 Karl Marx Avenue, 644024 Omsk, Russia
2. Dostoevsky Omsk State University,
55A Mir Avenue, 644077 Omsk, Russia
3. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: osiman@rambler.ru, urazovainn@mail.ru, jkochet@math.nsc.ru

Received May 29, 2018
Revised June 4, 2019
Accepted June 5, 2019

References

[1] Y. Wakabayashi, Aggregation of Binary Relations: Algorithmic and Polyhedral Investigations, Master Thesis (Universität Augsburg, West Germany, 1986).

[2] J. Brimberg, S. Janicijevic, S. Mladenovic, and D. Urosevic, Solving the clique partitioning problem as a maximally diverse grouping problem, Optim. Lett. 11, 1123–1135 (2017).

[3] M. J. Brusco and H. F. Kohn, Clustering qualitative data based on binary equivalence relations: Neighborhood search heuristics for the clique partitioning problem, Psychometrika 74, 685–703 (2009).

[4] F. Marcotorchino and P. Michaud, Heuristic approach to the similarity aggregation problem, Methods Oper. Res. 43, 395–404 (1981).

[5] I. Ham, K. Hitomi, and T. Yoshida, Group Technology: Applications to Production Management (Kluwer Acad. Publ., Dordrecht, 1988).

[6] M. Oosten, J. H. G. C. Rutten, and F. C. R. Spieksma, The clique partitioning problem: Facets and patching facets, J. Networks 38 (4), 209–226 (2001).

[7] S. Fortunato, Community detection in graphs, Phys. Rep. 486 (3), 75–174 (2010).

[8] S. Bocker, S. Briesemeister, and G. W. Klau, Exact algorithms for cluster editing: Evaluation and experiments, Algorithmica 60, 316–334 (2011).

[9] M. Grotschel and Y. Wakabayashi, A cutting plane algorithm for a clustering problem, Math. Program., Ser. B 45, 59–96 (1989).

[10] M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope, Math. Program. 47, 367–387 (1990).

[11] M. Grotschel and Y. Wakabayashi, Composition of facets of the clique partitioning polytope, in Topics in Combinatorics and Graph Theory, (Physica-Verlag, Heidelberg, 1990), pp. 271–284.

[12] R. Yu. Simanchev and I. V. Urazova, On the faces of the graph approximation problem polytope, Diskretn. Anal. Issled. Oper. 22 (2), 86–101 (2015) [Russian] [J. Appl. Industr. Math. 9 (2), 283–291 (2015)].

[13] I. V. Urazova and R. Yu. Simanchev, Separation problem for k-parashutes, in Supp. Proc. DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Vol. 1623 (Vladivostok, 2016), pp. 109–114. Available at http://ceur-ws.org/Vol-1623/paperco16.pdf.

[14] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2, 143–146 (1955).

[15] G. Sh. Fridman, A graph approximation problem, Upravlyaemye Sistemy 8, 73–75 (1971) [Russian].

[16] C. T. Zahn, Approximating symmetric relations by equivalence relations, J. Soc. Indust. Appl. Math. 12 (4), 840–847 (1964).

[17] M. Krivánek and J. Morávek, NP-hard problems in hierarchical-tree clustering, Acta Inform. 23, 311–323 (1986).

[18] N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Machine Learning 56, 89–113 (2004).

[19] A. Ben-Dor, R. Shamir, and Z. Yakhimi, Clustering gene expression patterns, J. Comput. Biol. 6 (3–4), 281–297 (1999).

[20] R. Shamir, R. Sharan, and D. Tsur, Cluster graph modification problems, Discrete Appl. Math. 44 (1-2), 173–182 (2004).

[21] A. A. Ageev, V. P. Il’ev, A. V. Kononov, and A. S. Talevnin, Computational complexity of the graph approximation problem, Diskretn. Anal. Issled. Oper. 13 (1), 3–11 (2006) [Russian] [J. Appl. Indust. Math. 1 (1), 1–8 (2007)].

[22] M. Charikar, V. Guruswami, and A. Wirth, Clustering with qualitative information, J. Comput. Syst. Sci. 71 (3), 360–383 (2005).

[23] I. Giotis and V. Guruswami, Correlation clustering with a fixed number of clusters, Theory Comput. 2 (1), 249–266 (2006).

[24] N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and clustering, J. ACM 55 (5), 1–27 (2008).

[25] A. van Zuylen and D. P. Williamson, Deterministic pivoting algorithms for constrained ranking and clustering problems, Math. Oper. Res. 34 (3), 594–620 (2009).

[26] R. Yu. Simanchev and I. V. Urazova, Scheduling unit-time jobs on the parallel processors polytope, Diskretn. Anal. Issled. Oper. 18 (11), 85–97 (2011) [Russian].

[27] M. W. Padberg and G. Rinaldi, Facet identification for the symmetric traveling salesman polytope, Math. Programming 47, 219-257 (1990).

[28] R. M. Karp and C. H. Papadimitriu, On linear characterizations of combinatorial optimization problems, SIAM J. Comput. 11, 620–632 (1982).

[29] E. Alekseeva, Yu. Kochetov, and A. Plyasunov, Complexity of local search for the $p$-median problem, Eur. J. Oper. Res. 191, 736–752 (2008).

[30] S. Iellamo, E. Alekseeva, L. Chen, M. Coupechoux, and Yu. Kochetov, Competitive location in cognitive radio networks, 4OR 13 (1), 81–110 (2015).

[31] N. Mladenovic, J. Brimberg, P. Hansen, and J. A. Moreno-Pérez, The $p$-median problem: A survey of metaheuristic approaches, Eur. J. Oper. Res. 179 (3), 927–939 (2007).

[32] Z. Diakova and Yu. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron Notes Discrete Math. 39, 29–34 (2012).