A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs. (February 2018)

• Record Type: Journal Article
• Authors: Nogueira, Bruno; Pinheiro, Rian G.S.
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 232
• Page End: 248
• Publication Date: 2018-02
• Subjects: Combinatorial optimization -- Clique -- Maximum weight clique -- GPU -- Local search -- Metaheuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.023
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We propose a new neighborhood structure for the problem. The results demonstrate that our neighborhood structure is better than the current ones, and it has the additional benefit that it can be explored using a GPU-based massively parallel architecture. We are the first to study the use of a GPU on the problem. The results indicate that an up to 12x speedup can be achieved. We compare our heuristic with the state-of-the-art ones and show that, even when the heuristic executes without using a GPU, it outperforms them. Abstract: Given an undirected graph with positive weights on the vertices, the Maximum Weight Clique Problem (MWCP) consists in finding a clique with maximum total weight. In this paper, we present a CPU-GPU local search heuristic for solving the MWCP on massive graphs. The heuristic is based on two new neighborhood structures for the problem. These neighborhoods are explored using an efficient procedure that is suitable to be mapped onto a GPU-based massively parallel architecture. We test the proposed heuristic on real-world massive graphs with millions of edges and vertices. The results indicate that, even when the heuristic is executed on a CPU-only architecture, it is able to outperform the best-known heuristics for the MWCP. Moreover, the hybrid CPU-GPU implementation obtained an average speedup of up to 12 times over the CPU-only implementation.