VI ALIO/EURO Workshop on Applied Combinatorial Optimization

December 15 - 17, 2008, Buenos Aires, Argentina

Formulations and Algorithms for Vertex Coloring Problems

Paolo Toth

DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy


Keywords: Vertex Coloring Problem, Bin Packing Problem, Integer Linear Programming, Exact algorithms, Bounding procedures, Metaheuristic algorithms

We present Integer Linear Programming formulations, exact algorithms, lower bounding procedures and Metaheuristic algorithms for two important Coloring Problems: the classical Vertex Coloring Problem and the Bounded Vertex Coloring Problem.

Given an undirected graph G = (V,E), where V is the vertex set and E the edge set, the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. The VCP is a well known NP-hard problem with real world applications in many engineering fields, including scheduling, timetabling, register allocation, frequency assignment and communication networks.

In the Bounded Vertex Coloring Problem (BVCP), we are given an undirected conflict graph G = (V, E), where edge (i, j) belongs to E if an only if vertices i and j are in conflict. We are also given a non negative weight for each vertex of V, and an infinite number of identical bins having a weight capacity C. The aim of the BVCP is to assign all the vertices to the minimum number of bins, so that the total weight of the vertices assigned to a bin does not exceed the bin capacity C, and no bin contains vertices in conflict. The problem is also called Bin Packing Problem with Conflicts. The BVCP generalizes both the "Bin Packing Problem" (BPP) and the classical VCP. The BPP is a special case of the BVCP arising when no vertex is in conflict with the other vertices (i.e., when the edge set E is empty). The VCP is a special case of the BVCP arising when all the vertices have weight equal to zero (i.e., when the bin capacity C is infinite). Real-world applications of the BVCP include examination scheduling, assignment of processes to processors, and load balancing of tasks in parallel computing. It also concerns particular delivery problems, such as food distribution, where some items cannot be placed in the same vehicle.

The most effective algorithms proposed for the VCP and the BVCP are considered. Extensive computational experiments on benchmark instances from the literature are reported.