2013

Two lagrangian relaxation based heuristics for vertex coloring problem

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

PDF

___

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