An Efficient Cooperative Scatter Search for the Large-Scale k-Clustering Minimum Biclique Completion Problem

Abstract

The k-Clustering Minimum Biclique Completion Problem (k-CMBCP) is an NP-hard combinatorial optimization problem with significant implications in bipartite graph clustering applications. The objective is to partition a set of services into k disjoint clusters such that the number of missing edges required to transform each cluster into a complete biclique is minimized. This paper proposes a robust Cooperative Scatter Search (CSS) algorithm designed to exploit the structural characteristics of the problem. The proposed metaheuristic framework integrates a diversification-based population initialization strategy, dynamic management of elite reference set, and a specialized uniform-based recombination operator. Furthermore, the algorithm incorporates a sequential Variable Neighborhood Descent (VND) strategy leveraging three complementary neighborhoods to intensify the local search. The contribution is a problem-tailored integration of known search ingredients rather than a generic new metaheuristic paradigm: its novelty lies in the way diversification, reference-set memory, recombination, and SeqVND are coordinated for the specific structure of the k-CMBCP. Computational experiments on benchmark instances show that the proposed method achieves competitive and superior performance compared with recent heuristics in terms of solution quality and computational stability.