A new branch-and-bound algorithm for the Maximum Weighted Clique Problem. (October 2019)

• Record Type: Journal Article
• Authors: San Segundo, Pablo; Furini, Fabio; Artieda, Jorge
• Is Part Of: Computers & operations research. Volume 110(2019)
• Page Start: 18
• Page End: 33
• Publication Date: 2019-10
• Subjects: Maximum Weighted Clique Problem -- Branch-and-Bound algorithm -- Computational results; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.05.017
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A new incremental bound for the Maximum Weighted Clique Problem based on an independent set cover. A Branch-and-Bound exact algorithm for the MaximumWeighted Clique Problem. Extensive computational experiments. Abstract: We study the Maximum Weighted Clique Problem (MWCP), a generalization of the Maximum Clique Problem in which weights are associated with the vertices of a graph. The MWCP calls for determining a complete subgraph of maximum weight. We design a new combinatorial branch-and-bound algorithm for the MWCP, which relies on an effective bounding procedure. The size of the implicit enumeration tree is largely reduced via a tailored branching scheme, specifically conceived for the MWCP. The new bounding function extends the classical MWCP bounds from the literature to achieve a good trade off between pruning potential and computing effort. We perform extensive tests on random graphs, graphs from the literature and real-world graphs, and we computationally show that our new exact algorithm is competitive with the state-of-the-art algorithms for the MWCP in all these classes of instances.