A Branch-and-Cut Algorithm for the Partition Coloring Problem

Let G = (V, E) be an undirected graph, where E is the set of edges and V is the set of vertices. Furthermore, let Q = {Q1,..., Qq} be a partition of V into q subsets such that Q1 ∪... ∪ Qq = V and Qi∩Qj = ∅, for all i, j = 1,..., q with i � = j. We refer to Q1,..., Qq as the components of the partition, while P [v] denotes the index of the component of vertex v ∈ V. The Partition Coloring Problem (PCP) consists in finding a subset of vertices V ′ ⊆ V such that |V ′ ∩ Qi | = 1, i = 1,..., q (i.e., V ′ contains one vertex from each component Qi, i = 1,..., q), and the chromatic number of the graph induced in G by V ′ is minimum. This problem is clearly a generalization of the graph coloring problem. Li and Simha [6] have shown that the decision version of PCP is NP-complete. Algorithms for solving PCP have been used in the literature as building blocks for algorithms for the Routing and Wavelength Assignment (RWA) problem in optical networks. In such networks, each signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. Wavelength Division Multiplexing (WDM) allows the more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. An all-optical point-to-point connection between two vertices is called a lightpath. Two lightpaths may use the same wavelength