Iterated local search with tabu search for the weighted vertex coloring problem. (English) Zbl 1458.90619

Summary: This paper proposes an iterated local search (ILS) based heuristic for the weighted vertex coloring problem (WVCP). Given a graph \(G(V,E)\) with a weight \(w(v)\) associated with each vertex \(v\in V\), the WVCP asks to find a coloring \(\{V_1,\dots,V_k\}\) of \(G\) that minimizes \(\sum_{i=1}^k\max_{v\in V_i}w(v)\). This problem has many theoretical and practical applications, such as batch scheduling, buffer minimization, and traffic assignment in telecommunication. Our ILS heuristic relies on two new neighborhood structures for the problem, and its local search component is hybridized with a tabu search strategy. We compare our approach with state-of-the-art heuristics and exact methods for the problem. Experimental results on well-known benchmark instances demonstrate that, first, our heuristic is better than the other heuristics in both solution quality and computational time, and, second, it is a good alternative for large instances that cannot be solved by exact methods.


90C35 Programming involving graphs or networks
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Avanthay, C.; Hertz, A.; Zufferey, N., A variable neighborhood search for graph coloring, European Journal of Operational Research, 151, 2, 379-388 (2003) · Zbl 1053.90050
[2] Bahiense, L.; Frota, Y.; Noronha, T. F.; Ribeiro, C. C., A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives, Discrete Applied Mathematics, 164, 34-46 (2014) · Zbl 1321.05251
[3] Cornaz, D.; Furini, F.; Malaguti, E., Solving vertex coloring problems as maximum weight stable set problems, Discrete Applied Mathematics, 217, 151-162 (2017) · Zbl 1358.05098
[4] Furini, F.; Malaguti, E., Exact weighted vertex coloring via branch-and-price, Discrete Optimization, 9, 2, 130-136 (2012) · Zbl 1246.90129
[5] Galinier, P.; Hertz, A., A survey of local search methods for graph coloring, Computers & Operations Research, 33, 9, 2547-2562 (2006) · Zbl 1086.90060
[6] Gendreau, M., Potvin, J.-Y., 2010. Handbook of Metaheuristics, Springer. Ch. Tabu Search, pp. 41-60. · Zbl 1198.90002
[7] Hollander, M.; Wolfe, D. A.; Chicken, E., Nonparametric Statistical Methods (2014), John Wiley & Sons · Zbl 1279.62006
[8] Jin, Y.; Hao, J.-K.; Hamiez, J.-P., A memetic algorithm for the minimum sum coloring problem, Computers & Operations Research, 43, 318-327 (2014) · Zbl 1348.90598
[9] Kavitha, T.; Mestre, J., Max-coloring paths: tight bounds and extensions, Journal of Combinatorial Optimization, 24, 1, 1-14 (2012) · Zbl 1254.90272
[10] Lourenço, H.R., Martin, O.C., Stützle, T., 2010. Handbook of Metaheuristics, Springer. Ch. Iterated Local Search: Framework and Applications, pp. 363-397.
[11] Malaguti, E.; Toth, P., A survey on vertex coloring problems, International Transactions in Operational Research, 17, 1, 1-34 (2010) · Zbl 1223.05079
[12] Malaguti, E.; Monaci, M.; Toth, P., Models and heuristic algorithms for a weighted vertex coloring problem, Journal of Heuristics, 15, 5, 503-526 (2009) · Zbl 1189.90180
[13] Morgenstern, C., Distributed coloration neighborhood search, Discrete Mathematics and Theoretical Computer Science, 26, 335-358 (1996) · Zbl 0864.90123
[14] Morgenstern, C., Shapiro, H., 1990. Coloration neighborhood structures for general graph coloring. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 226-235. · Zbl 0800.68609
[15] Nogueira, B.; Pinheiro, R. G., A cpu-gpu local search heuristic for the maximum weight clique problem on massive graphs, Computers & Operations Research, 90, 232-248 (2018) · Zbl 1391.90527
[16] Nogueira, B.; Pinheiro, R. G., A gpu based local search algorithm for the unweighted and weighted maximum s-plex problems, Annals of Operations Research, 1-34 (2019)
[17] Nogueira, B.; Pinheiro, R. G.; Subramanian, A., A hybrid iterated local search heuristic for the maximum weight independent set problem, Optimization Letters, 12, 3, 567-583 (2018) · Zbl 1401.90250
[18] Pemmaraju, S. V.; Raman, R., Approximation algorithms for the max-coloring problem, (International Colloquium on Automata, Languages, and Programming (2005), Springer), 1064-1075 · Zbl 1085.68114
[19] Pemmaraju, S.V., Raman, R. Varadarajan, K., 2004. Buffer minimization using max-coloring. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 562-571. · Zbl 1318.68129
[20] Prais, M.; Ribeiro, C. C., Reactive grasp: An application to a matrix decomposition problem in tdma traffic assignment, INFORMS Journal on Computing, 12, 3, 164-176 (2000) · Zbl 1040.90504
[21] Sun, W.; Hao, J.-K.; Lai, X.; Wu, Q., Adaptive feasible and infeasible tabu search for weighted vertex coloring, Information Sciences, 466, 203-219 (2018) · Zbl 1441.05211
[22] Wang, Y., Cai, S., Pan, S., Li, X., Yin, M., 2020. Reduction and local search for weighted graph coloring problem. In: The AAAI Conference on Artificial Intelligence.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.