Geodesic
The branch and cut method for~the~clique~partitioning~problem
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 60-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2019_26_3_a3,
     author = {R. Yu. Simanchev and I. V. Urazova and Yu. A. Kochetov},
     title = {The branch and cut method for~the~clique~partitioning~problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {60--87},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_3_a3/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
AU  - I. V. Urazova
AU  - Yu. A. Kochetov
TI  - The branch and cut method for~the~clique~partitioning~problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 60
EP  - 87
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_3_a3/
LA  - ru
ID  - DA_2019_26_3_a3
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%A I. V. Urazova
%A Yu. A. Kochetov
%T The branch and cut method for~the~clique~partitioning~problem
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 60-87
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_3_a3/
%G ru
%F DA_2019_26_3_a3
R. Yu. Simanchev; I. V. Urazova; Yu. A. Kochetov. The branch and cut method for~the~clique~partitioning~problem. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 60-87. http://geodesic.mathdoc.fr/item/DA_2019_26_3_a3/

[1] Wakabayashi Y., Aggregation of binary relations: Algorithmic and polyhedral investigations, Master Thesis, Univ. Augsburg, West Germany, 1986 | Zbl

[2] Brimberg J., Janicijevic S., Mladenovic N., Urosevic D., “Solving the clique partitioning problem as a maximally diverse grouping problem”, Optim. Lett., 11 (2017), 1123–1135 | DOI | MR | Zbl

[3] Brusco M. J., Kohn H. F., “Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem”, Psychometrika, 74 (2009), 685–703 | DOI | MR | Zbl

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

[5] Ham I., Hitomi K., Yoshida T., Group technology: applications to production management, Kluwer Acad. Publ., Dordrecht, 1988

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

[7] Fortunato S., “Community detection in graphs”, Phys. Rep., 486:3 (2010), 75–174 | DOI | MR

[8] Bocker S., Briesemeister S., Klau G. W., “Exact algorithms for cluster editing: evaluation and experiments”, Algorithmica, 60 (2011), 316–334 | DOI | MR | Zbl

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

[10] Grotschel M., Wakabayashi Y., “Facets of the clique partitioning polytope”, Math. Program., 47 (1990), 367–387 | DOI | MR | Zbl

[11] Grotschel M., Wakabayashi Y., “Composition of facets of the clique partitioning polytope”, Topics in Combinatorics and Graph Theory, Physica-Verl., Heidelberg, 1990, 271–284 | DOI | MR

[12] R. Yu. Simanchev, I. V. Urazova, “On the faces of the graph approximation problem polytope”, J. Appl. Industr. Math., 9:2 (2015), 283–291 | DOI | MR | Zbl

[13] Urazova I. V., Simanchev R. Yu., “Separation problem for $k$-parachutes”, Supp. Proc. DOOR (Vladivostok, Russia, Sept. 19–23, 2016), CEUR Workshop Proceedings, 1623, 2016, 109–114 http://ceur-ws.org/Vol-1623/paperco16.pdf

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

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

[16] Zahn C. T., “Approximating symmetric relations by equivalence relations”, J. Soc. Ind. Appl. Math., 12:4 (1964), 840–847 | DOI | MR | Zbl

[17] Křivánek M., Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Inform., 23 (1986), 311–323 | DOI | MR

[18] Bansal N., Blum A., Chawla S., “Correlation clustering”, Machine Learn., 56 (2004), 89–113 | DOI | MR | Zbl

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

[20] Shamir R., Sharan R., Tsur D., “Cluster graph modification problems”, Discrete Appl. Math., 144:1–2 (2004), 173–182 | DOI | MR | Zbl

[21] A. A. Ageev, V. P. Il'ev, A. V. Kononov, A. S. Talevnin, “Computational complexity of the graph approximation problem”, J. Appl. Indust. Math., 1:1 (2007), 1–8 | DOI

[22] Charikar M., Guruswami V., Wirth A., “Clustering with qualitative information”, J. Comput. Syst. Sci., 71:3 (2005), 360–383 | DOI | MR | Zbl

[23] Giotis I., Guruswami V., “Correlation clustering with a fixed number of clusters”, Theory Comput., 2:1 (2006), 249–266 | DOI | MR | Zbl

[24] Ailon N., Charikar M., Newman A., “Aggregating inconsistent information: ranking and clustering”, J. ACM, 55:5 (2008), 1–27 | DOI | MR

[25] Van Zuylen A., Williamson D. P., “Deterministic pivoting algorithms for constrained ranking and clustering problems”, Math. Oper. Res., 34:3 (2009), 594–620 | DOI | MR | Zbl

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

[27] Padberg M. W., Rinaldi G., “Facet identification for the symmetric traveling salesman polytope”, Math. Program., 47 (1990), 219–257 | DOI | MR | Zbl

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

[29] Alekseeva E., Kochetov Yu., Plyasunov A., “Complexity of local search for the $p$-median problem”, Eur. J. Oper. Res., 2008, no. 191, 736–752 | DOI | MR | Zbl

[30] Iellamo S., Alekseeva E., Chen L., Coupechoux M., Kochetov Yu., “Competitive location in cognitive radio networks”, 4OR, 13:1 (2015), 81–110 | DOI | MR | Zbl

[31] Mladenović N., Brimberg J., Hansen P., Moreno-Pérez J. A., “The $p$-median problem: a survey of metaheuristic approaches”, Eur. J. Oper. Res., 179:3 (2007), 927–939 | DOI | MR | Zbl

[32] Diakova Z., Kochetov Yu., “A double VNS heuristic for the facility location and pricing problem”, Electron. Notes Discrete Math., 2012, no. 39, 29–34 | DOI | MR | Zbl