Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4960118 | European Journal of Operational Research | 2017 | 14 Pages |
Abstract
The Maximum Vertex Weight Clique Problem (MVWCP) is an important generalization of the well-known NP-hard Maximum Clique Problem. In this paper, we introduce a generalized move operator called PUSH, which generalizes the conventional ADD and SWAP operators commonly used in the literature and can be integrated in a local search algorithm for MVWCP. The PUSH operator also offers opportunities to define new search operators by considering dedicated candidate push sets. To demonstrate the usefulness of the proposed operator, we implement two simple tabu search algorithms which use PUSH to explore different candidate push sets. The computational results on 142 benchmark instances from different sources (DIMACS, BHOSLIB, and Winner Determination Problem) indicate that these algorithms compete favorably with the leading MVWCP algorithms.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Yi Zhou, Jin-Kao Hao, Adrien Goƫffon,