  


Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
Stefano Gualandi (stefano.gualandiunipv.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 branchandprice 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 bestknown 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):81100, 2012. DOI: 10.1287/ijoc.1100.0436 Download: [PDF] Entry Submitted: 03/12/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  