Two lagrangian relaxation based heuristics for vertex coloring problem

Year 2020, Volume: 41 Issue: 2, 493 - 505, 25.06.2020

Ali İrfan Mahmutoğulları

https://doi.org/10.17776/csj.628518

Abstract

Vertex coloring problem is a well-known NP-Hard problem where the objective is to minimize the number of colors used to color vertices of a graph ensuring that adjacent vertices cannot have same color. In this paper, we first discuss existing mathematical formulations of the problem and then consider two different heuristics, namely HEUR-RA and HEUR-RC, based on Lagrangian relaxation of adjacency and coloring constraints. HEUR-RA does not require solving any optimization problem through execution whereas at each iteration of HEUR-RC another NP-Hard problem, maximal weight stable set problem, is solved. We conduct experiments to observe computational performances of these heuristics. The experiments reveal that although it requires longer running times, HEUR-RC outperforms HEUR-RA since it provides lower optimal gaps as well as upper bound information.

Keywords

Vertex coloring problem, heuristics, optimization

References

• [1] Karp R. M., Reducibility among combinatorial problems. Springer (1972).
• [2] Diestel R., Graph theory (graduate texts in mathematics). Springer (2005).
• [3] Brown J. R., Chromatic scheduling and the chromatic number problem. Management Science, 19 (4) (1972) 456–463.
• [4] Brélaz D., New methods to color the vertices of a graph. Communications of the ACM, 220 (4) (1979) 251–256.
• [5] Sewell E., An improved algorithm for exact graph coloring. DIMACS series in discrete mathematics and theoretical computer science, 26 (1996) 359-373.
• [6] Mehrotra A. and Trick M. A., A column generation approach for graph coloring. Informs Journal on Computing, 80 (4) (1996) 344–354.
• [7] Méndez-Diaz I. and Zabala P., A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 1540 (5) (2006) 826-847.
• [8] Méndez-Diaz I. and Zabala P., A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 1560 (2) (2008) 159-179.
• [9] Leighton F. T., A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 840 (6) (1979) 489–506.
• [10] Bollobás B. and Thomason A., Random graphs of small order. North-Holland Mathematics Studies, 118 (1985) 47-97.
• [11] Culberson J. C. and Luo F., Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26 (1996) 245–284.
• [12] Morgenstern C., Distributed coloration neighborhood search. Discrete Mathematics and Theoretical Computer Science, 26 (1996) 335–358.
• [13] Chiarandini M., Dumitrescu I., and Stützle T., Stochastic local search algorithms for the graph colouring problem. Handbook of approximation algorithms and metaheuristics. Chapman & Hall, CRC (2007).
• [14] Hertz A. and de Werra D., Using tabu search techniques for graph coloring. Computing, 390 (4) (1987) 345–351.
• [15] Johnson D. S., Aragon C. R., McGeoch L. A. and Schevon C., Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, 370 (6) (1989) 865–892.
• [16] Malaguti E. and Toth P., A survey on vertex coloring problems. International Transactions in Operational Research, 170 (1) (2010) 1–34.
• [17] Mehrotra A., Constrained graph partitioning: decomposition, polyhedral structure and algorithms, (1992).
• [18] Hansen P., Labbé M. and Schindl D., Set covering and packing formulations of graph coloring: algorithms and first polyhedral results. Discrete Optimization, 60 (2) (2009) 135–147.
• [19] Wolsey L.A., Integer programming. Wiley (1998).