Treffer: A set packing model for the Partition Coloring Problem.

In this paper we propose a set packing model for the Partition Coloring Problem (PCP) a generalization of the Vertex Coloring Problem (VCP). Given a graph whose vertex set is partitioned in clusters, PCP aims to select one vertex from each cluster such that the chromatic number of the resulted induced subgraph is minimal. A set packing integer linear programming formulation is presented and, based on this, we implement a branch-and-price algorithm. The resulted formulation offers a very good quality root linear relaxation problem. Computational experiments led on instances from literature and on newly generated instances for the problem of routing and wavelength assignment in all-optical networks show that our algorithm performs at least as well and sometimes better than the state-of-the-art algorithms for large instances. We introduce a version of this algorithm based on strengthening the root linear relaxation with cuts using two families of valid inequalities which proved to be effective for small and medium instances. [ABSTRACT FROM AUTHOR]