Solving the list coloring problem through a branch-and-price algorithm. (English) Zbl 07895428
Summary: In this work, we present a branch-and-price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. We propose two branching strategies based on others for the Graph Coloring Problem, the first is an adaptation of the one used by Mehrotra and Trick in their pioneering branch-and-price algorithm and the other is inspired by the one used by Méndez-Díaz and Zabala in their branch-and-cut algorithm. The rich structure of this problem makes both branching strategies robust. Extensive computation experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.
MSC:
| 90Bxx | Operations research and management science |
Software:
CPLEXReferences:
| [1] | Archetti, C.; Bianchessi, N.; Hertz, A., A branch-and-price algorithm for the robust graph coloring problem, Discrete Applied Mathematics, 165, 49-59, 2014 · Zbl 1288.05077 |
| [2] | Biró, M.; Hujter, M.; Tuza, Z., Precoloring extension. I. Interval graphs, Discrete Mathematics, 100, 1, 267-279, 1992 · Zbl 0766.05026 |
| [3] | Björklund, A.; Husfeldt, T.; Koivisto, M., Set partitioning via inclusion-exclusion, SIAM Journal on Computing, 39, 2, 546-563, 2009 · Zbl 1215.05056 |
| [4] | Bonomo, F.; Cecowski Palacio, M., Between coloring and list-coloring: \( \mu \)-coloring, Ars Combinatoria, 99, 383-398, 2011 · Zbl 1265.05214 |
| [5] | Brélaz, D., New methods to color the vertices of a graph, Communications of the ACM, 22, 251-256, 1979 · Zbl 0394.05022 |
| [6] | Chvátal, V.; Hoàng, C. T.; Mahadev, N. V.R.; De Werra, D., Four classes of perfectly orderable graphs, Journal of Graph Theory, 11, 4, 481-495, 1987 · Zbl 0654.05032 |
| [7] | Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M., Parameterized algorithms, 2015, Springer Publishing Company · Zbl 1334.90001 |
| [8] | DIMACS Challenges, M., Graph coloring instances, 2002, Retrieved from https://mat.gsia.cmu.edu/COLOR04/. (Accessed 23 February 2023) |
| [9] | Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213, 2002 · Zbl 1049.90004 |
| [10] | Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19, 2, 248-264, 1972 · Zbl 0318.90024 |
| [11] | Furini, F.; Gabrel, V.; Ternier, I.-C., An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem, Networks, 69, 1, 124-141, 2017 · Zbl 1388.05063 |
| [12] | Furini, F.; Malaguti, E., Exact weighted vertex coloring via branch-and-price, Discrete Optimization, 9, 2, 130-136, 2012 · Zbl 1246.90129 |
| [13] | Garey, M.; Johnson, D. S., Computers and intractability; a guide to the theory of NP-completeness, 1979, W. H. Freeman · Zbl 0411.68039 |
| [14] | Garling, D. J.H., Inequalities: a journey into linear analysis, 2007, Cambridge University Press · Zbl 1135.26014 |
| [15] | Golovach, P. A.; Johnson, M.; Paulusma, D.; Song, J., A survey on the computational complexity of coloring graphs with forbidden subgraphs, Journal of Graph Theory, 84, 4, 331-363, 2017 · Zbl 1359.05039 |
| [16] | Gomes, C. P.; Selman, B., Problem structure in the presence of perturbations, (Proceedings of aAAI’97/iAAI’97, 1997, AAAI Press: AAAI Press Providence, RI, USA), 221-226 |
| [17] | Held, S.; Cook, W.; Sewell, E. C., Safe lower bounds for graph coloring, (Proceedings of IPCO 2011, 2011, Springer: Springer New York, NY, USA), 261-273 · Zbl 1341.05074 |
| [18] | Ibm, S., ILOG CPLEX Optimization Studio 12.7, 2016, Retrieved from https://www.ibm.com/products/ilog-cplex-optimization-studio. (Accessed 23 February 2023) |
| [19] | Kubale, M., Graph colorings, 2004, American Mathematical Soc. · Zbl 1064.05061 |
| [20] | Lucci, M.; Nasini, G.; Severín, D., Planning the workday of bus drivers by a graph list-coloring model, Electronic Journal of SADIO (EJS), 17, 1, 77-91, 2018 |
| [21] | Lucci, M.; Nasini, G.; Severín, D., A branch and price algorithm for list coloring problem, Electronic Notes in Theoretical Computer Science, 346, 613-624, 2019 · Zbl 07515216 |
| [22] | Malaguti, E.; Monaci, M.; Toth, P., An exact approach for the vertex coloring problem, Discrete Optimization, 8, 2, 174-190, 2011 · Zbl 1244.05092 |
| [23] | Mehrotra, A.; Trick, M. A., A column generation approach for graph coloring, INFORMS Journal on Computing, 8, 4, 344-354, 1996 · Zbl 0884.90144 |
| [24] | Méndez-Díaz, I.; Zabala, P., A branch-and-cut algorithm for graph coloring, Discrete Applied Mathematics, 154, 5, 826-847, 2006 · Zbl 1120.90034 |
| [25] | OR-Library, I., Set covering instances, 2018, Retrieved from http://people.brunel.ac.uk/ mastjjb/jeb/orlib/scpinfo.html. (Accessed 23 February 2023) |
| [26] | Tuza, Z., Graph colorings with local constraints - a survey, Discussiones Mathematicae. Graph Theory, 17, 2, 161-228, 1997 · Zbl 0923.05027 |
| [27] | Zykov, A. A., On some properties of linear complexes, Matematicheskii sbornik, 66, 2, 163-188, 1949 · Zbl 0033.02602 |
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.
