A Variable Neighborhood Search heuristic for the maximum ratio clique problem

Consider a graph in which every vertex has two non-negative weights. In this graph, the maximum ratio clique problem (MRCP) searches for a maximal clique that maximizes a fractional function defined by the ratio of the sums of vertex weights. It has been proved that MRCP is NP-hard and, consequently, it is difficult to solve MRCP by exact methods. Due to this fact, we present the first heuristic approach, i.e., a multi-start Variable Neighborhood Search (MS-VNS) algorithm. In order to verify the performance of our MS-VNS, we use standard instances and according to our observations, our MS-VNS approach provides high-quality solutions in a short computation time. Furthermore, on most of the instances, our algorithm outperforms the classical methods that have already been used for solving MRCP.