An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

Baiyu Chen; Junwen Ding; Canhui Luo; Qingyun Zhang; Zhouxing Su; Zhipeng Lü

doi:10.1609/aaai.v39i25.34895

An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

Baiyu Chen
, Junwen Ding
, Canhui Luo
, Qingyun Zhang^*
, Zhouxing Su
, Zhipeng Lü

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time. Copyright © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Original language	English
Title of host publication	Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence
Editors	Toby Walsh, Julie Shah, Zico Kolter
Publisher	AAAI Press
Pages	26904-26912
Number of pages	9
ISBN (Print)	1-57735-897-X, 978-1-57735-897-8
DOIs	https://doi.org/10.1609/aaai.v39i25.34895
Publication status	Published - 2025
Externally published	Yes
Event	39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025) - Pennsylvania Convention Center , Philadelphia, United States Duration: 25 Feb 2025 → 4 Mar 2025 https://aaai.org/conference/aaai/aaai-25/

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	Association for the Advancement of Artificial Intelligence
ISSN (Print)	2159-5399

Conference

Conference	39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025)
Abbreviated title	AAAI-25
Place	United States
City	Philadelphia
Period	25/02/25 → 4/03/25
Internet address	https://aaai.org/conference/aaai/aaai-25/

Funding

We are grateful to the anonymous reviewers for their helpful comments. This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 6240072662, 72101094 and 62202192, the Special Project for Knowledge Innovation of Hubei Province under Grant 2022013301015175, and Interdiciplinary Research Program of Hust 5003300129.

Access Output

10.1609/aaai.v39i25.34895

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, B., Ding, J., Luo, C., Zhang, Q., Su, Z., & Lü, Z. (2025). An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem. In T. Walsh, J. Shah, & Z. Kolter (Eds.), Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (pp. 26904-26912). (Proceedings of the AAAI Conference on Artificial Intelligence). AAAI Press. https://doi.org/10.1609/aaai.v39i25.34895

@inproceedings{2a916bea24304774ad77afde7f1a05ff,

title = "An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem",

abstract = "The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time. Copyright {\textcopyright} 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",

author = "Baiyu Chen and Junwen Ding and Canhui Luo and Qingyun Zhang and Zhouxing Su and Zhipeng L{\"u}",

year = "2025",

doi = "10.1609/aaai.v39i25.34895",

language = "English",

isbn = "1-57735-897-X",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

pages = "26904--26912",

editor = "Walsh, \{Toby \} and Julie Shah and Zico Kolter",

booktitle = "Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence",

note = "39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025), AAAI-25 ; Conference date: 25-02-2025 Through 04-03-2025",

url = "https://aaai.org/conference/aaai/aaai-25/",

}

Chen, B, Ding, J, Luo, C, Zhang, Q, Su, Z & Lü, Z 2025, An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem. in T Walsh, J Shah & Z Kolter (eds), Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, pp. 26904-26912, 39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025), Philadelphia, Pennsylvania, United States, 25/02/25. https://doi.org/10.1609/aaai.v39i25.34895

An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem. / Chen, Baiyu; Ding, Junwen; Luo, Canhui et al.
Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence. ed. / Toby Walsh; Julie Shah; Zico Kolter. AAAI Press, 2025. p. 26904-26912 (Proceedings of the AAAI Conference on Artificial Intelligence).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

AU - Chen, Baiyu

AU - Ding, Junwen

AU - Luo, Canhui

AU - Zhang, Qingyun

AU - Su, Zhouxing

AU - Lü, Zhipeng

PY - 2025

Y1 - 2025

N2 - The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time. Copyright © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

AB - The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time. Copyright © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

UR - http://www.scopus.com/inward/record.url?scp=105003904519&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105003904519&origin=recordpage

U2 - 10.1609/aaai.v39i25.34895

DO - 10.1609/aaai.v39i25.34895

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 1-57735-897-X

SN - 978-1-57735-897-8

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 26904

EP - 26912

BT - Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence

A2 - Walsh, Toby

A2 - Shah, Julie

A2 - Kolter, Zico

PB - AAAI Press

T2 - 39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025)

Y2 - 25 February 2025 through 4 March 2025

ER -

Chen B, Ding J, Luo C, Zhang Q, Su Z, Lü Z. An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem. In Walsh T, Shah J, Kolter Z, editors, Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press. 2025. p. 26904-26912. (Proceedings of the AAAI Conference on Artificial Intelligence). Epub 2025 Apr 11. doi: 10.1609/aaai.v39i25.34895

An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

Abstract

Publication series

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this