New Integer Linear Programming Models for the Vertex Coloring Problem
New Integer Linear Programming Models for the Vertex Coloring Problem
复制标题
DOI：
10.1007/978-3-319-77404-6_47
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Adalat Jabrayilov;Petra Mutzel
中科院分区：
文献类型：
--
作者：
Adalat Jabrayilov;Petra Mutzel
顶点着色问题要求给定图的顶点可以被分配的颜色的最小数量，使得每两个邻居具有不同的颜色。这个问题是NP难的。在这里，我们介绍了新的整数线性规划公式的基础上偏序。它们的优点是，它们与经典的分配公式一样简单，因为它们可以直接输入标准的整数线性规划求解器。我们评估我们的新模型，使用Guidelines和表明，我们的新的简单的方法是一个很好的替代最好的国家的最先进的方法的顶点着色问题。在我们的计算实验中，我们比较我们的配方与经典的分配配方和代表配方上的一个大的基准图，以及随机生成的图形的大小和密度不同。评估表明，基于偏序的模型占主导地位的稀疏图的配方，而代表配方是最好的稠密图。
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 neighbors have different colors. The problem is NP-hard. Here, we introduce new integer linear programming formulations based on partial-ordering. They have the advantage that they are as simple to work with as the classical assignment formulation, since they can be fed directly into a standard integer linear programming solver. We evaluate our new models using Gurobi and show that our new simple approach is a good alternative to the best state-of-the-art approaches for the vertex coloring problem. In our computational experiments, we compare our formulations with the classical assignment formulation and the representatives formulation on a large set of benchmark graphs as well as randomly generated graphs of varying size and density. The evaluation shows that the partial-ordering based models dominate both formulations for sparse graphs, while the representatives formulation is the best for dense graphs.