The Design, Analysis, and Implementation of Parallel Simulated Annealing and Parallel Genetic Algorithms for the Composite Graph Coloring Problem

The composite graph coloring problem (CGCP) is similar to the standard graph coloring problem (SGCP). Associated with each vertex of a composite graph is a positive integer which represents the chromaticity of that vertex. This number is the number of consecutive integers (colors) which must be assigned to the vertex. The goal of the CGCP is to color the graph with as few colors as possible. The largest integer used in the coloring is called the chromatic number of the graph. The CGCP is proven to be NP-complete. Exact, heuristic, and stochastic methods are analyzed and compared. Exact methods are limited to small graphs and heuristic methods are lacking in quality. Two stochastic methods, genetic algorithms and simulated annealing, are applied to the CGCP. Both methods are implemented for MIMD parallel computers. To aid in finding the best parameter settings for the two stochastic methods, a least squares parameter optimization method is presented. The two stochastic methods use the same solution space setup where each point in the solution space is represented by a list of the vertices of the graph in some order. Solutions to the CGCP are given by coloring the graph using these orders of the vertices in the basic-vertex-sequential algorithm. It is proven that the optimal solution is given by coloring the graph with the basic-vertex-sequential algorithm with some order of the vertices. Both stochastic methods only generate feasible solutions when searching the solution space for the optimal order of the vertices. The stochastic methods perform superior to the heuristic methods for random graphs of fifty and one-hundred vertices. Testing on larger graphs was limited because of the amount of parallel computing resources available. It is believed that given a sufficient amount of computing time, the stochastic methods would be superior for all graph sizes