A Cross Entropy Algorithm For Maximum Clique Problem And On It's Parallelization Study

The maximum clique problem (MCP) is a classical combinatorial optimization problem, and finds many important applications in different domains, this paper surveys the current progress on MCP.The Cross Entropy(CE) method for combinatorial optimization is proposed by Reuven Y. Rubinstein. The CE method is new approach for combinatorial optimization, and has rapidly developed into a powerful and versatile technique. The basic idea behind the CE method is to transform the original (combinatorial or otherwise) optimization problem to an associated stochastic optimization problem, and then to tackle the stochastic optimization efficiently by an adaptive sampling algorithm based on Kullback-Leibler cross-entropy, importance sample and Boltzmann function.This paper introduces a new CE algorithm for MCP. Based on the CE framework, an algorithm for MCP is designed and implemented. The Fitness Distance Correlation(FDC) is adopted to analyze the algorithm's behavior, and an improvement is proposed to enhance its performance based on the results. As the general CE framework is based on large mount simulation, it's a time-consuming approach. To speedup the algorithm, this paper designed and implemented two parallel algorithms using OpenMP and MPI. To make use of MPI, this paper introduced a leader-base parallel strategy. To test the performance of CE algorithm, empirical experiments on 80 DIMACS graph instances is shown. To compare with other best heuristic approaches, 27 instances is selected. Experimental results on DIMACS problems show that this new computing algorithm obtains competitive results. And the numerical results of parallel algorithm showed that the parallel computing approach is effective and efficient.