Enrico
Malaguti
Title:
A set-covering based approach for a weighted vertex coloring
problem
Abstract:
Enrico Malaguti, Michele Monaci, Paolo Toth
We approach a
weighted version of the well known Vertex Coloring Problem (VCP) where
each vertex i of a graph G has associated a positive weight w(i). Like
in the classical VCP, one has to assign a color to each vertex i in
such a way that colors on adjacent vertices are different. The
objective is to minimize the sum of the costs of colors used, where in
this problem the cost of each color is the maximum weight of the
vertices that are assigned the color itself. The problem is known to be
NP-hard and arises in practical scheduling applications, where it is
also known as Time Slot Scheduling of Compatible Jobs. We present a
two-phase approach to the problem based on the "Set-Covering" (SC)
formulation, in which variables are associated with feasible
assignments of a color (i.e., each column corresponds to a stable set).
In the first phase (column generation) we generate a large amount of
feasible solutions by means of fast greedy heuristics designed for the
problem; every generated solution can be improved using two fast post
optimization procedures, the first based on the optimal solution of an
Integer Linear Programming model, the second on the solution of an
Assignment Problem; in the second phase (column optimization) an
associated set-covering instance is solved by using a Lagrangian-based
heuristic algorithm from the literature. Computational results on
instances from the literature are reported.