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

作     者：Gualandi, Stefano Malucelli, Federico 

作者机构：Politecn Milan Dipartimento Elettr & Informat I-20133 Milan Italy 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (美国运筹学与管理学会计算杂志)

年 卷 期：2012年第24卷第1期

页      面：81-100页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：column generation integer linear programming constraint programming graph coloring 

摘      要：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.