Improving Simulated Annealing for Clique Partitioning Problems

Jian Gao, Yiqi Lv, Minghao Liu, Shaowei Cai, Feifei Ma

TL;DR

This paper introduces an enhanced simulated annealing algorithm (SACC) for the Clique Partitioning Problem (CPP). By incorporating a novel timestamp-based configuration checking strategy to prevent search cycles and a descent search method to improve local search capabilities, SACC significantly outperforms existing state-of-the-art algorithms, setting new best solutions for 34 benchmark instances.

What Problem Does This Paper Address?

The Clique Partitioning Problem (CPP) is a crucial problem in graph theory with applications in areas like community detection and resource allocation. It involves partitioning the vertices of a complete edge-weighted graph into cliques such that the sum of edge weights within these cliques is maximized. Due to its NP-hard nature, finding optimal solutions for large-scale instances is computationally infeasible. While simulated annealing (SA) is a popular heuristic for CPP, it can suffer from getting trapped in local optima and cycling through previously visited states, hindering its efficiency and effectiveness, especially for massive graphs. This paper aims to address these limitations by proposing improvements to SA to make it more efficient and robust for solving large-scale CPP instances.

Methods

The core of this paper is the development of an improved simulated annealing algorithm called SACC. The key novelties include:

  • Timestamp-based Configuration Checking: Traditional configuration checking methods struggle with complete graphs. The authors propose a new strategy that uses timestamps to track when vertices move between clusters and when clusters are updated. This allows for efficient detection and prevention of search cycles by forbidding a vertex from returning to a cluster if no new vertices have been added to that cluster since its departure. This strategy is implemented with O(1) time complexity per check.
  • Descent Search Method: To enhance the local search capability of SA, a descent search method is integrated. After SA finds a potential solution, this method performs a local search to further optimize it by exploring the neighborhood and finding a better solution. This compensates for SA's tendency to miss local optima.
  • Iterated Simulated Annealing Framework: SACC employs an iterated local search framework. It repeatedly applies the SA with configuration checking, gradually decreasing the initial temperature (shrinking mechanism) to accelerate convergence.
  • Restart Strategy: To prevent the algorithm from getting stuck in a local optimum and to encourage exploration of new solution spaces, a restart mechanism is incorporated. If the algorithm fails to find an improvement within a certain number of iterations, it restarts with a new random initial solution.

Datasets

The authors evaluated their algorithm on a set of 94 benchmark instances for the Clique Partitioning Problem. These instances were sourced from previous research and include a range of sizes, with vertex counts varying from 100 to 7000. The instances were categorized into "small" (less than 1000 vertices) and "large" (1000 or more vertices).

Key Insights and Ideas

  • Configuration Checking for Complete Graphs: The paper highlights that standard configuration checking methods are not directly applicable to complete graphs due to the nature of vertex neighborhoods. The timestamp-based approach effectively addresses this by focusing on cluster updates rather than just vertex movements.
  • Synergy of SA and Descent Search: Combining SA's ability to escape local optima with a descent search's power to refine solutions in the local neighborhood leads to a significant improvement in solution quality.
  • Importance of Iteration and Restart: The iterated nature of the algorithm, coupled with a restart mechanism, is crucial for exploring the solution space more thoroughly and avoiding premature convergence to suboptimal solutions, especially for complex instances.
  • Effectiveness on Large-Scale Instances: The proposed SACC algorithm demonstrates a remarkable ability to find high-quality solutions for large and challenging CPP instances, often outperforming existing methods.

Key Results

  • SACC achieved state-of-the-art performance on the tested benchmark instances.
  • It updated the best-known solutions for 34 out of 94 instances.
  • For large-scale instances (≥ 1000 vertices), SACC found the best solutions for 44 instances, significantly outperforming other algorithms.
  • SACC demonstrated superior performance in terms of both solution quality and the number of times the best solution was found (hit times) compared to algorithms like MDMCP, TMLS_SA, and CPP-P3.
  • Statistical analysis (Wilcoxon signed-rank test) confirmed that SACC's results are significantly better than those of other algorithms on large-scale instances.
  • The parameter atemp controlling the temperature shrinking speed was found to be relatively insensitive within a certain range, but the shrinking mechanism itself was crucial for performance.
  • The restart mechanism was shown to be essential for preventing the algorithm from converging prematurely and ensuring satisfactory results, especially for larger instances.

Limitations and Future Work

  • Limitations: While SACC performs exceptionally well, the paper notes that for some small instances, multiple algorithms can achieve equally good solutions, indicating that these instances might be "easy" to solve. The performance on extremely large instances (beyond 7000 vertices) is not explicitly discussed.
  • Future Work: The authors suggest future research could explore combining other metaheuristics with their proposed strategies to further enhance efficiency in solving the CPP. They also mention that future work might involve studies on combining other metaheuristics to solve the CPP more efficiently.

Summary updated

Abstract

The Clique Partitioning Problem (CPP) is essential in graph theory with a number of important applications. Due to its NP-hardness, efficient algorithms for solving this problem are very crucial for practical purposes, and simulated annealing is proved to be effective in state-of-the-art CPP algorithms. However, to make simulated annealing more efficient to solve large-scale CPPs, in this paper, we propose a new iterated simulated annealing algorithm. Several methods are proposed in our algorithm to improve simulated annealing. First, a new configuration checking strategy based on timestamp is presented and incorporated into simulated annealing to avoid search cycles. Afterwards, to enhance the local search ability of simulated annealing and speed up convergence, we combine our simulated annealing with a descent search method to solve the CPP. This method further improves solutions found by simulated annealing, and thus compensates for the local search effect. To further accelerate the convergence speed, we introduce a shrinking factor to decline initial temperature and then propose an iterated local search algorithm based on simulated annealing. Additionally, a restart strategy is adopted when the search procedure converges. Extensive experiments on benchmark instances of the CPP were carried out, and the results suggest that the proposed simulated annealing algorithm outperforms all the existing heuristic algorithms, including five state-of-the-art algorithms. Thus the best-known solutions for 34 instances out of 94 are updated. We also conduct comparative analyses of the proposed strategies and show their effectiveness.
BibTeX
@article{gao2022improving,
  author = {Jian Gao and Yiqi Lv and Minghao Liu and Shaowei Cai and Feifei Ma},
  title = {{Improving Simulated Annealing for Clique Partitioning Problems}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13382},
}
Figure