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/