In addressing the evolving landscape of cell clustering methodologies, this paper unveils a pioneering strategy leveraging the Variable Neighborhood Search (VNS) metaheuristic. The motivation behind this exploration lies in the need to tackle the intricate task of clustering cells based on both gene expression and spatial coordinates. To present a comprehensive solution, we initially cast the cell clustering challenge as an Integer Linear Programming (ILP) minimization problem, harnessing the robust foundation of VNS. Our proposed approach introduces a novel model based on the VNS technique, demonstrating its efficacy in navigating the complexities inherent in cell clustering. Notably, our method transcends the confines of conventional cell type clustering, as evidenced by our initial results, extending its application to spatial domain clustering. This inherent adaptability enables our algorithm to orchestrate clusters based on information gleaned from both gene expression matrices and spatial coordinates. Validation through rigorous testing underscores the superior performance of our method when compared to existing techniques chronicled in the literature. In summary, our project not only advances the current progress of clustering methodologies but also holds immense potential for transformative applications across diverse fields, from biomedical research to spatial data analysis. The overall benefits of our approach underscore its capacity to significantly impact and propel scientific investigation forward.
