Optimization Online


Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

Stefano Gualandi (stefano.gualandi***at***unipv.it)
Federico Malucelli (malucell***at***elet.polimi.it)

Abstract: We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

Keywords: Column Generation, Integer Linear Programming, Constraint Programming, Graph Coloring

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: S. Gualandi, F. Malucelli. Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation. INFORMS Journal on Computing, 24(1):81-100, 2012. DOI: 10.1287/ijoc.1100.0436

Download: [PDF]

Entry Submitted: 03/12/2010
Entry Accepted: 03/12/2010
Entry Last Modified: 09/14/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society