Research map / Learning theory and algorithms / Combinatorial and search optimization
An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes EWSA, an elite-guided weighted simulated annealing metaheuristic for the clique partitioning problem that alternates two configurations via an oscillation strategy, using weighted acceptance, partition restriction, and elite preservation.
Problem
The clique partitioning problem (CPP): partition the vertices of a complete edge-weighted graph to maximize total within-clique edge weight; NP-hard, with large instances hard for exact methods.
Approach
Combines a weighted simulated annealing acceptance rule (weighting by vertex non-move counts) with two alternating configurations (diversifying and elite-refining) chosen by an oscillation rate, plus an adaptive partition-number restriction and elite reset with tabu-like similarity checks.
Key results
- Improves best known upper bounds on 32 of 255 instances and matches BKS on 223, with no worse solutions.
- On 94 challenging random-weight instances, EWSA achieves best results on 94 (best) vs 77 for SACC, 67 for FSS, 57 for MDMCP in terms of best objective values per Table 4 counts.
- Ablation over 26 instances shows each component (weighting, two configurations, elite preservation, partition restriction) contributes; EWSA beats all variants on most instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the weighting strategy in WSA (ablation) | EWSA · 26 representative second-category instances | objective value: 20 wins, 4 losses (best); 25 wins, 1 loss (average) | Helped |
| use both configurations with oscillation instead of config1 only (ablation) | EWSA · 26 representative second-category instances | objective value: 25 wins, 0 losses (best); 26 wins, 0 losses (average) | Helped |
| use both configurations with oscillation instead of config2 only (ablation) | EWSA · 26 representative second-category instances | objective value: 26 wins, 0 losses (best); 26 wins, 0 losses (average) | Helped |
| add the elite solution preservation mechanism (ablation) | EWSA · 26 representative second-category instances | objective value: 15 wins, 5 losses (best); 22 wins, 4 losses (average) | Helped |
| use the partition restriction strategy instead of adaptive partitioning (ablation) | EWSA · 26 representative second-category instances | objective value: 15 wins, 6 losses (best); 14 wins, 12 losses (average) | Mixed |
Surprising findings
- Elite-guided refinement alone (EWSAc2) performs worst in the ablation, while the combined oscillation is best.
Limitations
- Gains concentrated on large-scale random-weight instances; small real-world instances are all matched rather than improved.
- SACC was not re-run because its source code was unavailable; comparison uses reported results with a CPU speed adjustment.
Experimental setup
Datasets: CPP benchmark instances (161 real-world-derived and 94 random-weight instances)
Benchmarks: CPP benchmark instances (255 total: 161 first category, 94 second category)
Metrics: best objective value average objective value hit rate Wilcoxon signed-rank p-value
Baselines: SACC FSS MDMCP ITS CPP-P3 TMLS-SA
Builds on: simulated annealing MDMCP SACC
Closest papers by meaning
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.84)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.83)
- Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem (AAAI 2024 · similarity 0.83)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.82)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.