TL;DR
This paper introduces EWSA, a novel algorithm for the Clique Partitioning Problem (CPP) that balances exploration and exploitation using two distinct search configurations and an adaptive oscillation strategy. EWSA also incorporates a unique weighting mechanism into simulated annealing and an adaptive partition restriction to improve search efficiency and discover better solutions.
What Problem Does This Paper Address?
The Clique Partitioning Problem (CPP) is a notoriously difficult NP-hard problem that involves dividing the vertices of a complete, edge-weighted undirected graph into subsets (cliques) such that the sum of edge weights within each clique is maximized. This problem has broad applications in fields like image processing, social network analysis, and biological computing. While exact methods can guarantee optimality, they struggle with large-scale instances. Existing metaheuristic approaches, though effective, still leave room for improvement, particularly in finding optimal solutions for larger and more complex problem instances within reasonable timeframes. This paper aims to address this by proposing a more efficient and effective metaheuristic algorithm.
Methods
EWSA is built upon a Simulated Annealing (SA) framework, enhanced with several novel components:
- Dual Search Configurations with Oscillation: EWSA employs two distinct configurations:
- Config1 (Exploratory Diversification): Designed to explore the solution space broadly and discover new potential elite solutions. It uses a lower percentage of stable vertices for initial temperature calculation and a specific scoring function (sc=1) to encourage diversification.
-
Config2 (Elite-guided Intensification): Focused on refining the current elite solution. It uses a higher percentage of stable vertices for initial temperature and a different scoring function (sc=2) for intensification. An oscillation strategy adaptively switches between these configurations based on the quality of the current elite solution and the elapsed time, aiming for a balanced trade-off between exploration and exploitation.
-
Weighted Simulated Annealing (WSA): A new scoring function is introduced for SA. This function incorporates not only the change in objective value and current temperature but also a "weight" representing how many iterations a vertex has not been moved. This weighting aims to smooth the search process, prevent premature convergence, and enhance diversification.
- Adaptive Partition Number Restriction: To reduce the search space and improve efficiency, EWSA dynamically sets an upper bound on the number of partitions (Kpr). This bound is based on the number of partitions in the historical best solution, plus an allowance for an empty partition. This strategy prevents the search from exploring an excessively large number of partitions.
- Elite Solution Preservation: To prevent the search from getting stuck in local optima, especially when using Config2, a mechanism is implemented to periodically reset the elite solution if no improvement is seen for a certain number of iterations. This mechanism also incorporates a tabu-like strategy to avoid revisiting previously explored elite solutions.
Datasets
The paper evaluates EWSA on 255 instances. These are categorized into:
- First category (161 instances): Primarily derived from real-world applications, including aggregation of binary relations, machine cell formation, and cluster editing. These are described as smaller and easier to solve.
- Second category (94 instances): Challenging instances with random weights.
The paper references existing benchmarks and datasets, particularly mentioning Sørensen and Letchford (2024) and Jovanovic, Sanfilippo, and Voß (2023) for the first category and citing MDMCP, FSS, and SACC as prior works that have used similar benchmarks.
Key Insights and Ideas
- The power of adaptive oscillation: The paper demonstrates that dynamically switching between exploration-focused and exploitation-focused search strategies is crucial for effectively navigating the complex CPP search space. The adaptive rate ensures the algorithm doesn't get stuck in either extreme.
- Weighting for smoother SA: Incorporating vertex "inactivity" into the SA scoring function is a clever way to combat premature convergence and encourage exploration, especially in the later stages of the search.
- Partition restriction as a speed-up: Dynamically limiting the number of partitions significantly prunes the search space, leading to faster convergence and improved efficiency without sacrificing solution quality.
- Synergy of components: The experiments with EWSA variants strongly suggest that each proposed component (weighting, dual configurations, partition restriction, elite preservation) contributes significantly to the overall performance. Disabling any one component leads to a noticeable degradation in results.
Key Results
EWSA demonstrates strong performance on the tested instances:
- On 130 open instances: EWSA improved the best known results for 32 instances and matched the best known results for the remaining 98.
- On 125 closed instances (with known optimal solutions): EWSA found all the proven optimal solutions within a short computational time.
- Comparison with state-of-the-art algorithms (SACC, FSS, MDMCP):
- For the first category of 161 instances, EWSA achieved the best objective values on all instances and performed comparably on average objective values. Statistical tests (Wilcoxon signed ranks) showed no significant difference, likely due to the instances being easy.
- For the second category of 94 instances, EWSA significantly outperformed other algorithms, achieving better results more frequently and with a higher hitting rate.
- Variant analysis: EWSA consistently outperformed its variants (EWSAw, EWSAC1, EWSAC2, EWSAem, EWSApr) across various metrics, highlighting the importance of each proposed component.
Limitations and Future Work
- Limitations:
- The paper acknowledges that while EWSA performs well, there's always room for further improvement, especially for extremely large-scale instances.
- The performance of EWSA on the first category of instances (real-world applications) showed no statistically significant difference compared to other algorithms, likely because these instances are relatively easy to solve.
- Future Work:
- The paper doesn't explicitly detail future work directions, but the success of EWSA suggests potential avenues for applying its core ideas (adaptive oscillation, weighted SA, adaptive partition restriction) to other combinatorial optimization problems.
- Further exploration of different oscillation strategies or more sophisticated elite preservation mechanisms could be explored.
Summary updated