论文标题
加强基于部分订购的ILP模型，用于顶点着色问题
Strengthened Partial-Ordering Based ILP Models for the Vertex Coloring Problem
论文作者
论文摘要
顶点着色问题要求将最小颜色数量分配给给定图的顶点，以使每个相邻的顶点都会获得不同的颜色。对于这个NP硬性问题，已经提出了各种整数线性编程（ILP）模型。其中，由于简单性和易于扩展性，基于任务的ILP模型和基于部分订购的ILP模型具有吸引力。此外，在稀疏图上，这两种模型都是解决顶点着色问题的最强精确方法之一。在这项工作中，我们建议针对基于部分订购的ILP模型的额外加强约束，并表明它们导致相应LP弛豫的下限改善。我们的计算实验证实，新的约束也导致了实际的改进。特别是，我们能够从DIMAC基准设置的顶点着色问题的基准中找到先前打开的实例的最佳解决方案
The vertex coloring problem asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. For this NP-hard problem, a variety of integer linear programming (ILP) models have been suggested. Among them, the assignment based and the partial-ordering based ILP models are attractive due to their simplicity and easy extendability. Moreover, on sparse graphs, both models turned out to be among the strongest exact approaches for solving the vertex coloring problem. In this work, we suggest additional strengthening constraints for the partial-ordering based ILP model, and show that they lead to improved lower bounds of the corresponding LP relaxation. Our computational experiments confirm that the new constraints are also leading to practical improvements. In particular, we are able to find the optimal solution of a previously open instance from the DIMACS benchmark set for vertex coloring problems
