Exact weighted vertex coloring via branch‐and‐price

Exact weighted vertex coloring via branch‐and‐price

0.00 Avg rating0 Votes
Article ID: iaor20124030
Volume: 9
Issue: 2
Start Page Number: 130
End Page Number: 136
Publication Date: May 2012
Journal: Discrete Optimization
Authors: ,
Keywords: optimization, scheduling
Abstract:

We consider the Weighted Vertex Coloring Problem (WVCP), in which a positive weight is associated to each vertex of a graph. In WVCP, one is required to assign a color to each vertex in such a way that colors on adjacent vertices are different, and the objective is to minimize the sum of the costs of the colors used, where the cost of each color is given by the maximum weight of the vertices assigned to that color. This NP‐hard problem arises in practical scheduling applications, where it is also known as Scheduling on a Batch Machine with Job Compatibilities. We propose the first exact algorithm for the problem, which is based on column generation and branch‐and‐price. Computational results on a large set of instances from the literature are reported, showing excellent performance when compared with the best heuristic algorithms from the literature.

Reviews

Required fields are marked *. Your email address will not be published.