×

zbMATH — the first resource for mathematics

A supernodal formulation of vertex colouring with applications in course timetabling. (English) Zbl 1207.05046
Summary: For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using “supernodes”.
In the definition of A. George and D. R. McIntyre [SIAM J. Numer. Anal. 15, 90–112 (1978; Zbl 0389.65014)], a “supernode” is a complete. subgraph, within which every pair of vertices have the same neighbourhood outside of the subgraph. A polynomial-time algorithm for obtaining the best possible partition of an arbitrary graph into supernodes is given. This makes it possible to use any formulation of vertex multicolouring to encode vertex colouring. Results of empirical tests on benchmark instances in graph colouring (DIMACS) and timetabling (Udine Course Timetabling) are also provided and discussed.

MSC:
05C15 Coloring of graphs and hypergraphs
90C10 Integer programming
Software:
CALMA; DIMACS; SCIP; YSMP; Zimpl
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aardal, K. I., Hoesel, S. P. M., van Koster, A. M. C. A., & Mannino, C. (2007). Models and solution techniques for frequency assignment problems. Annals of Operation Research, 153, 79–129. · Zbl 1157.90005 · doi:10.1007/s10479-007-0178-0
[2] Achlioptas, D., & Naor, A. (2005). The two possible values of the chromatic number of a random graph. Annals of Mathematics, 163(3), 1333–1349. · Zbl 1094.05048
[3] Achterberg, T. (2007). Constraint integer programming. Unpublished doctoral dissertation, Berlin. · Zbl 1169.90414
[4] Appa, G., Magos, D., & Mourtos, I. (2005). On the system of two all_different predicates. Information Processing Letters, 94(3), 99–105. · Zbl 1182.68141 · doi:10.1016/j.ipl.2005.01.009
[5] Avella, P., & Vasil’ev, I. (2005). A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8(6), 497–514. · Zbl 1123.90016 · doi:10.1007/s10951-005-4780-1
[6] Barbosa, V. C., & Szwarcfiter, J. L. (1999). Generating all the acyclic orientations of an undirected graph. Information Processing Letters, 72, 71–74. · Zbl 1339.05379 · doi:10.1016/S0020-0190(99)00120-9
[7] Barbosa, V. C., Assis, C. A. G., & Nascimento, J. O. do. (2004). Two novel evolutionary formulations of the graph coloring problem. Journal of Combinatorial Optimization, 8(1), 41–63. · Zbl 1057.05030 · doi:10.1023/B:JOCO.0000021937.26468.b2
[8] Beyrouthy, C. B., Burke, E. K., Silva, D. L., McCollum, B., McMullan, P., & Parkes, A. J. (2008). Towards improving the utilisation of university teaching space. Journal of the Operational Research Society, 60(1), 130–143. · Zbl 1168.90499 · doi:10.1057/palgrave.jors.2602523
[9] Bollobás, B. (2001). Random graphs. Cambridge: Cambridge University Press. · Zbl 0979.05003
[10] Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280. · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3
[11] Burke, E. K., Werra, D., & Kingston, J. H. (2004). Applications to timetabling. In J. L. Gross & J. Yellen (Eds.), Handbook of graph theory (pp. 445–474). Boca Raton: CRC Press.
[12] Burke, E. K., Mareček, J., Parkes, A. J., & Rudová, H. (2008). Penalising patterns in timetables: novel integer programming formulations. In S. Nickel & J. Kalcsics (Eds.), Operations research proceedings 2007 (pp. 409–414). Berlin: Springer. · Zbl 1209.90160
[13] Campêlo, M., Corrêa, R. C., & Frota, Y. (2003). Cliques, holes and the vertex coloring polytope. Information Processing Letters, 89(4), 159–164. · Zbl 1176.90598 · doi:10.1016/j.ipl.2003.11.005
[14] Campêlo, M., Campos, V. A., & Corrêa, R. C. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156(7), 1097–1111. · Zbl 1138.05020 · doi:10.1016/j.dam.2007.05.058
[15] Campêlo, M., Campos, V. A., & Corrêa, R. C. (2009). Um algoritmo de planos-de-corte para o número cromático fracionário de um grafo. Pesquisa Operacional, 29(1), 179–193.
[16] Caprara, A. (1998). Properties of some ilp formulations of a class of partitioning problems. Discrete Applied Mathematics, 87(1–3), 11–23. · Zbl 0910.90217 · doi:10.1016/S0166-218X(98)00046-8
[17] Carter, M. W., & Laporte, G. (1997). Recent developments in practical course timetabling. In E. K. Burke & M. W. Carter (Eds.), LNCS: Vol. 1408. Practice and theory of automated timetabling (pp. 3–19). Berlin: Springer.
[18] Catanzaro, D., Godi, A., & Labbé, M. (2008). A class representative model for pure parsimony haplotyping (Tech. Rep. Nos. Dated October 29, 2008). Bruxelles, Belgium: Université Libre de Bruxelles. · Zbl 1243.90134
[19] Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (2006). The strong perfect graph theorem. Annals of Mathematics, 164(1), 51–229. · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[20] Coll, P., Marenco, J., Méndez-Díaz, I., & Zabala, P. (2002). Facets of the graph coloring polytope. Annals of Operation Research, 116, 79–90. · Zbl 1013.90097 · doi:10.1023/A:1021315911306
[21] Crescenzi, P., Kann, V., Halldórsson, M., Karpinski, M., & Woeginger, G. (2005). A compendium of NP optimization problems (Available on-line).
[22] Cunningham, W. H., & Edmonds, J. (1980). A combinatorial decomposition theory. Canadian Journal of Mathematics, 32(3), 734–765. · Zbl 0442.05054 · doi:10.4153/CJM-1980-057-7
[23] Duff, I. S., & Reid, J. K. (1983). The multifrontal solution of indefinite sparse symmetric linear. ACM Transactions on Mathematical Software, 9(3), 302–325. · Zbl 0515.65022 · doi:10.1145/356044.356047
[24] Eisenstat, S. C., Elman, H. C., Schultz, M. H., & Sherman, A. H. (1984). The (new) yale sparse matrix package. In Elliptic problem solvers, II (Monterey, Calif., 1983), (pp. 45–52). San Diego: Academic Press. · Zbl 0562.65014
[25] Feige, U., & Kilian, J. (1998). Zero knowledge and the chromatic number. Journal of Computer and System Science, 57(2), 187–199. · Zbl 0921.68089 · doi:10.1006/jcss.1998.1587
[26] Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33(9), 2547–2562. · Zbl 1086.90060 · doi:10.1016/j.cor.2005.07.028
[27] Gallai, T. (1967). Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungar, 18, 25–66. · Zbl 0153.26002 · doi:10.1007/BF02020961
[28] Gallai, T. (1968). On directed paths and circuits. In P. Erdös & G. Katobna (Eds.), Theory of graphs (pp. 115–118). San Diego: Academic Press. · Zbl 0159.54403
[29] Garey, M. R., & Johnson, D. S. (1976). The complexity of near-optimal graph coloring. Journal of the ACM, 23(1), 43–49. · Zbl 0322.05111 · doi:10.1145/321921.321926
[30] Gaspero, L. D., & Schaerf, A. (2003). Multi neighborhood local search with application to the course timetabling problem. In E. K. Burke & P. D. Causmaecker (Eds.), LNCS: Vol. 2740. Practice and theory of automated timetabling (pp. 262–275). Berlin: Springer.
[31] Gaspero, L. D., & Schaerf, A. (2006). Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modelling and Algorithms, 5(1), 65–89. · Zbl 1103.90102 · doi:10.1007/s10852-005-9032-z
[32] Gebremedhin, A. H., Manne, F., & Pothen, A. (2005). What color is your Jacobian? Graph coloring for computing derivatives. SIAM Review, 47(4), 629–705. · Zbl 1076.05034 · doi:10.1137/S0036144504444711
[33] George, A., & McIntyre, D. R. (1978). On the application of the minimum degree algorithm to finite element systems. SIAM Journal of Numerical Analysis, 15(1), 90–112. · Zbl 0389.65014 · doi:10.1137/0715006
[34] Golumbic, M. C. (1977). The complexity of comparability graph recognition and coloring. Computing, 18(3), 199–208. · Zbl 0365.05025 · doi:10.1007/BF02253207
[35] Gross, J. L., & Yellen, J. (2004). Handbook of graph theory. Boca Raton: CRC Press. · Zbl 1036.05001
[36] Habib, M., & Maurer, M. C. (1979). On the X-join decomposition for undirected graphs. Discrete Applied Mathematics, 1(3), 201–207. · Zbl 0439.05041 · doi:10.1016/0166-218X(79)90043-X
[37] Hansen, P., Labbé, M., & Schindl, D. (2005). Set covering and packing formulations of graph coloring: algorithms and first polyhedral results (Tech. Rep. No. G-2005-76). Montreal, Canada: GERAD.
[38] Johnson, D. J., & Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, Workshop, October 11–13, 1993. Providence: American Mathematical Society.
[39] Kaibel, V., & Margot, F. (2007). Personal communication at MIP Workshop 2007 in Montreal, Canada.
[40] Kaibel, V., & Pfetsch, M. (2008). Packing and partitioning orbitopes. Mathematical Programming, 114(1), 1–36. doi: 10.1007/s10107-006-0081-5 . · Zbl 1171.90004 · doi:10.1007/s10107-006-0081-5
[41] Kaibel, V., Peinhardt, M., & Pfetsch, M. E. (2007). Orbitopal fixing. In M. Fischetti & D. P. Williamson (Eds.), LNCS: Vol. 4513. Integer programming and combinatorial optimization (pp. 74–88). New York: Springer. · Zbl 1136.90407
[42] Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum.
[43] Kiaer, L., & Yellen, J. (1992). Weighted graphs and university course timetabling. Computers Operations Research, 19(1), 59–67. · Zbl 0825.90529 · doi:10.1016/0305-0548(92)90059-E
[44] Koch, T. (2004). Rapid mathematical programming. Unpublished doctoral dissertation, Berlin (ZIB Technical Report TR-04-58).
[45] Krajíček, J. (1997). Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Journal of Symbolic Logic, 62(2), 457–486. · Zbl 0891.03029 · doi:10.2307/2275541
[46] Lee, J. (2002). All-different polytopes. Journal of Combinatorial Optimization, 6(3), 335–352. · Zbl 1007.90041 · doi:10.1023/A:1014804110661
[47] Lee, J., & Margot, F. (2007). On a binary-encoded ILP coloring formulation. INFORMS Journal of Computing, 19(3), 406–415. · Zbl 1241.90087 · doi:10.1287/ijoc.1060.0178
[48] Margot, F. (2002). Pruning by isomorphism in branch-and-cut. Mathematical Programming, 94, 71–90. · Zbl 1023.90088 · doi:10.1007/s10107-002-0358-2
[49] Margot, F. (2003). Exploiting orbits in symmetric ILP. Mathematical Programming, 98, 3–31. · Zbl 1082.90070 · doi:10.1007/s10107-003-0394-6
[50] Margot, F.: (2007). Symmetric ILP: Coloring and small integers. Discrete Optimization, 4, 40–62. · Zbl 1169.90411 · doi:10.1016/j.disopt.2006.10.008
[51] Mehrotra, A., & Trick, M. A. (1996). A column generation approach for graph coloring. INFORMS Journal of Computing, 8(4), 344–354. · Zbl 0884.90144 · doi:10.1287/ijoc.8.4.344
[52] Méndez-Díaz, I., & Zabala, P. (2008). A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 156, 2. · Zbl 1163.90012
[53] Möhring, R. H., & Radermacher, F. J. (1984). Substitution decomposition for discrete structures and connections with combinatorial optimization. In Algebraic and combinatorial methods in operations research (Vol. 95, pp. 257–355). Amsterdam: North-Holland. · Zbl 0567.90073
[54] Muller, J. H., & Spinrad, J. (1989). Incremental modular decomposition. Journal of the ACM, 36(1), 1–19. · Zbl 0671.68030 · doi:10.1145/58562.59300
[55] Murray, K., Müller, T., & Rudová, H. (2007). Modeling and solution of a complex university course timetabling problem. In E. K. Burke & H. Rudová (Eds.), LNCS: Vol. 3867. Practice and theory of automated timetabling (pp. 193–213). Berlin: Springer.
[56] Nešetřil, J., & Tardif, C. (2008). A dualistic approach to bounding the chromatic number of a graph. European Journal of Combinatorics, 29(1), 254–260. · Zbl 1126.05051 · doi:10.1016/j.ejc.2003.09.024
[57] Ostrowski, J., Linderoth, J., Rossi, F., & Smriglio, S. (2007). Orbital branching. In M. Fischetti & D. P. Williamson (Eds.), LNCS: Vol. 4513. Integer programming and combinatorial optimization (pp. 104–118). New York: Springer. · Zbl 1136.90411
[58] Petrovic, S., & Burke, E. K. (2004). University timetabling. In J. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis (pp. 1001–1023). Boca Raton: CRC Press.
[59] Prestwich, S. D. (2003). In E. Giunchiglia & A. Tacchella (Eds.), LNCS: Vol. 2919. Theory and applications of satisfiability testing (pp. 105–119). Berlin: Springer.
[60] Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graph. Revue AFIRO, 1, 127–132. · Zbl 0157.31302
[61] Rudová, H., & Murray, K. (2003). University course timetabling with soft constraints. In E. K. Burke & P. D. Causmaecker (Eds.), LNCS: Vol. 2740. Practice and theory of automated timetabling (pp. 310–328). Berlin: Springer.
[62] Sabidussi, G. (1961). Graph derivatives. Mathematische Zeitschrift, 76, 385–401. · Zbl 0109.16404 · doi:10.1007/BF01210984
[63] Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. · Zbl 05467698 · doi:10.1023/A:1006576209967
[64] Schimmelpfeng, K., & Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29, 783–803. · Zbl 1168.90670 · doi:10.1007/s00291-006-0074-z
[65] Schindl, D. (2004). Some combinatorial optimization problems in graphs with applications in telecommunications and tomography. Unpublished doctoral dissertation, Lausanne.
[66] Shapley, L. (1967). On committees. In New methods of thought and procedure (pp. 246–270). Berlin: Springer.
[67] Springer, D. L., & Thomas, D. E. (1994). Exploiting the special structure of conflict and compatibility graphs in high-level synthesis. IEEE Transactions on CAD of Integrated Circuits and Systems, 13(7), 843–856. · Zbl 05449744 · doi:10.1109/43.293941
[68] Vitaver, L. M. (1962). Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix. Doklady Akademii Nauk SSSR, 147, 758–759. · Zbl 0126.39302
[69] de Werra, D., & Hansen, P. (2003). Using stable sets to bound the chromatic number. Information Processing Letters, 87(3), 127–131. · Zbl 1161.68704 · doi:10.1016/S0020-0190(03)00266-7
[70] Williams, H. P., & Yan, H. (2001). Representations of the all_different predicate of constraint satisfaction in integer programming. INFORMS Journal of Computing, 13(2), 96–103. · Zbl 1238.90103 · doi:10.1287/ijoc.13.2.96.10515
[71] Zabala, P., & Méndez-Díaz, I. (2006). A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5), 826–847. · Zbl 1120.90034 · doi:10.1016/j.dam.2005.05.022
[72] Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6), 103–128. · Zbl 1213.68322 · doi:10.4086/toc.2007.v003a006
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.