A Branch-and-Price Approach for Graph Multi-Coloring
journal contributionposted on 1997-01-01, 00:00 authored by Anuj Mehrotra, Michael TrickMichael Trick
We present a branch-and-price framework for solving the graph multicoloring problem. We propose column generation to implicitly optimize the linear programming relaxation of an independent set formulation (where there is one variable for each independent set in the graph) for graph multi-coloring. This approach, while requiring the solution of a difficult subproblem, is a promising method to obtain good solutions for small to moderate size problems quickly. Some implementation details and initial computational experience are presented.