Two lagrangian relaxation based heuristics for vertex coloring problem

Ali İrfan Mahmutoğulları

doi:10.17776/csj.628518

EN

Two lagrangian relaxation based heuristics for vertex coloring problem

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).

Details

Primary Language

English

Subjects

-

Journal Section

Research Article

Authors

Ali İrfan Mahmutoğulları ^*
0000-0002-8770-8567
Türkiye

Publication Date

June 25, 2020

Submission Date

October 2, 2019

Acceptance Date

June 15, 2020

Published in Issue

Year 2020 Volume: 41 Number: 2

DOI

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

IZ

https://izlik.org/JA25CW39MC

Cite

RIS / Bibtex

APA

Mahmutoğulları, A. İ. (2020). Two lagrangian relaxation based heuristics for vertex coloring problem. Cumhuriyet Science Journal, 41(2), 493-505. https://doi.org/10.17776/csj.628518

AMA

1.Mahmutoğulları Aİ. Two lagrangian relaxation based heuristics for vertex coloring problem. CSJ. 2020;41(2):493-505. doi:10.17776/csj.628518

Chicago

Mahmutoğulları, Ali İrfan. 2020. “Two Lagrangian Relaxation Based Heuristics for Vertex Coloring Problem”. Cumhuriyet Science Journal 41 (2): 493-505. https://doi.org/10.17776/csj.628518.

EndNote

Mahmutoğulları Aİ (June 1, 2020) Two lagrangian relaxation based heuristics for vertex coloring problem. Cumhuriyet Science Journal 41 2 493–505.

IEEE

[1]A. İ. Mahmutoğulları, “Two lagrangian relaxation based heuristics for vertex coloring problem”, CSJ, vol. 41, no. 2, pp. 493–505, June 2020, doi: 10.17776/csj.628518.

ISNAD

Mahmutoğulları, Ali İrfan. “Two Lagrangian Relaxation Based Heuristics for Vertex Coloring Problem”. Cumhuriyet Science Journal 41/2 (June 1, 2020): 493-505. https://doi.org/10.17776/csj.628518.

JAMA

1.Mahmutoğulları Aİ. Two lagrangian relaxation based heuristics for vertex coloring problem. CSJ. 2020;41:493–505.

MLA

Mahmutoğulları, Ali İrfan. “Two Lagrangian Relaxation Based Heuristics for Vertex Coloring Problem”. Cumhuriyet Science Journal, vol. 41, no. 2, June 2020, pp. 493-05, doi:10.17776/csj.628518.

Vancouver

1.Ali İrfan Mahmutoğulları. Two lagrangian relaxation based heuristics for vertex coloring problem. CSJ. 2020 Jun. 1;41(2):493-505. doi:10.17776/csj.628518