×

A branch-and-price algorithm for the minimum sum coloring problem. (English) Zbl 1472.05049

Summary: A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
90C05 Linear programming
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-Noy, Amotz; Bellare, Mihir; Halldórsson, Magnús M.; Shachnai, Hadas; Tamir, Tami, On chromatic sums and distributed resource allocation, Inform. and Comput., 140, 2, 183-202 (1998) · Zbl 0895.68022
[2] Borndörfer, Ralf; Eisenblätter, Andreas; Grötschel, Martin; Martin, Alexander, The Orientation Model for Frequency Assignment ProblemsTechnical Report TR-98-01 (1998), ZIB: ZIB Takustr. 7, 14195 Berlin
[3] Campêlo, Manoel B.; Campos, Victor A.; Corrêa, Ricardo C., On the asymmetric representatives formulation for the vertex coloring problem, Discrete Appl. Math., 156, 7, 1097-1111 (2008) · Zbl 1138.05020
[4] Desrosiers, Jacques; Lübbecke, Marco E., (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer US: Springer US Boston, MA), chapter A Primer in Column Generation · Zbl 1246.90093
[5] Dolan, Elizabeth D.; Moré, Jorge J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[6] Furini, Fabio; Malaguti, Enrico; Martin, Sébastien; Ternier, Ian-Christopher, ILP models and column generation for the minimum sum coloring problem, Electron. Notes Discrete Math., 64, 215-224 (2018) · Zbl 1388.05064
[7] Gualandi, Stefano; Malucelli, Federico, Exact solution of graph coloring problems via constraint programming and column generation, INFORMS J. Comput., 24, 1, 81-100 (2012) · Zbl 1461.05091
[8] Gualandi, Stefano; Malucelli, Federico, A simple branching scheme for vertex coloring problems, Discrete Appl. Math., 160, 1, 192-196 (2012) · Zbl 1237.05075
[9] Hajiabolhassan, Hossein; Mehrabadi, Medhi; Tusserkani, Ruzbeh, Minimal coloring and strength of graphs, Discrete Math., 215, 1, 265-270 (2000) · Zbl 0957.05041
[10] Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas, Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs, Algorithmica, 37, 3, 187-209 (2003) · Zbl 1069.68531
[11] Hansen, Pierre; Labbé, Martine; Schindl, David, Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results, Discrete Optim., 6, 2, 135-147 (2009) · Zbl 1279.90115
[12] Held, Stephan; Cook, William J.; Sewell, Edward C., Maximum-weight stable sets and safe lower bounds for graph coloring, Math. Program. Comput., 4, 4, 363-381 (2012) · Zbl 1267.90005
[13] Anders Helmar, Marco Chiarandini, A local search heuristic for chromatic sum, in: Proceedings of the 9th Metaheuristics International Conference, Vol. 1101, 2011, pp. 161-170.
[14] Jin, Yan; Hamiez, Jean-Philippe; Hao, Jin-Kao, Algorithms for the minimum sum coloring problem: a review, Artif. Intell. Rev., 47, 3, 367-394 (2017)
[15] Jin, Yan; Hao, Jin-Kao, Hybrid evolutionary search for the minimum sum coloring problem of graphs, Inform. Sci., 352, 15-34 (2016) · Zbl 1398.68494
[16] Jin, Yan; Hao, Jin-Kao; Hamiez, Jean-Philippe, A memetic algorithm for the minimum sum coloring problem, Comput. Oper. Res., 43, 318-327 (2014) · Zbl 1348.90598
[17] Kroon, Leo G.; Sen, Arunabha; Deng, Haiyong; Roy, Asim, The optimal cost chromatic partition problem for trees and interval graphs, (d’Amore, Fabrizio; Franciosa, Paolo Giulio; Marchetti-Spaccamela, Alberto, Graph-Theoretic Concepts in Computer Science (1997), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 279-292
[18] Kubicka, Ewa; Schwenk, Allen J., An introduction to chromatic sums, (Computer Trends in the 1990s - Proceedings of the 1989 ACM 17th Annual Computer Science Conference, Louisville, Kentucky, USA, February 21-23, 1989 (1989)), 39-45
[19] Yu Li, Corinne Lucet, Aziz Moukrim, Kaoutar Sghiouer, Greedy algorithms for the minimum sum coloring problem, in: Logistique Et Transports, LT-027, Sousse, Tunisia, 2009.
[20] Lin, Weibo; Xiao, Mingyu; Zhou, Yi; Guo, Zhenyu, Computing lower bounds for minimum sum coloring and optimum cost chromatic partition, Comput. Oper. Res., 109, 263-272 (2019) · Zbl 1458.05078
[21] Malaguti, Enrico; Monaci, Michele; Toth, Paolo, An exact approach for the vertex coloring problem, Discrete Optim., 8, 2, 174-190 (2011) · Zbl 1244.05092
[22] Malaguti, Enrico; Toth, Paolo, A survey on vertex coloring problems, ITOR, 17, 1, 1-34 (2010) · Zbl 1223.05079
[23] Mehrotra, Anuj; Trick, Michael A., A column generation approach for graph coloring, INFORMS J. Comput., 8, 4, 344-354 (1996) · Zbl 0884.90144
[24] Méndez-Díaz, Isabel; Zabala, Paula, A polyhedral approach for graph coloring \({}^1\), Electron. Notes Discrete Math., 7, 178-181 (2001) · Zbl 0981.05040
[25] Mitchem, John; Morriss, Patrick, On the cost-chromatic number of graphs, Discrete Math., 171, 1-3, 201-211 (1997) · Zbl 0876.05031
[26] Moukrim, Aziz; Sghiouer, Kaoutar; Lucet, Corinne; Li, Yu, Lower bounds for the minimal sum coloring problem, Electron. Notes Discrete Math., 36, 663-670 (2010), ISCO 2010 - International Symposium on Combinatorial Optimization · Zbl 1237.90267
[27] Pan, Stefania; Calvo, Roberto Wolfler; Akplogan, Mahuna; Létocart, Lucas; Touati, Nora, A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints, Discrete Optim., 33, 146-168 (2019) · Zbl 1506.90108
[28] Salavatipour, Mohammad R., On sum coloring of graphs, Discrete Appl. Math., 127, 3, 477-488 (2003) · Zbl 1018.05035
[29] Sen, Arunabha; Deng, Haiyong; Guha, Sumanta, On a graph partition problem with application to VLSI layout, Inf. Process. Lett., 43, 2, 87-94 (1992) · Zbl 0764.68132
[30] Thomassen, Carsten; Erdös, Paul; Alavi, Yousef; Malde, Paresh J.; Schwenk, Allen J., Tight bounds on the chromatic sum of a connected graph, J. Graph Theory, 13, 3, 353-357 (1989) · Zbl 0677.05028
[31] Trick, Michael, Operations research page - vertex coloring instances (2019), https://mat.tepper.cmu.edu/COLOR/instances.html (Accessed: June 2019)
[32] Vanderbeck, Francois, On dantzig-wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm, Oper. Res., 48, 1, 111-128 (2000) · Zbl 1106.90360
[33] Wu, Qinghua; Hao, Jin-Kao, An effective heuristic algorithm for sum coloring of graphs, Comput. Oper. Res., 39, 7, 1593-1600 (2012) · Zbl 1250.05114
[34] Wu, Qinghua; Hao, Jin-Kao, Improved lower bounds for sum coloring via clique decomposition (2013), arXiv preprint arXiv:1303.6761 · Zbl 1278.90420
[35] Zykov, Alexander Aleksandrovich, On some properties of linear complexes, Mat. Sb., 66, 2, 163-188 (1949)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.