PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem
| Autor: | Jin-Kao Hao, Adrien Goëffon, Yi Zhou |
|---|---|
| Přispěvatelé: | Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), Institut Universitaire de France |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Vertex (graph theory)
Mathematical optimization Information Systems and Management General Computer Science Generalization 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Operator (computer programming) Clique problem 0202 electrical engineering electronic engineering information engineering tabu search Heuristics Local search (optimization) Mathematics 021103 operations research business.industry Local search [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Tabu search Cliques Modeling and Simulation Benchmark (computing) 020201 artificial intelligence & image processing business |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, Elsevier, 2017, 257 (1), pp.41-54. ⟨10.1016/j.ejor.2016.07.056⟩ |
| ISSN: | 0377-2217 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect