zbMATH — the first resource for mathematics

Exact solution of graph coloring problems via constraint programming and column generation. (English) Zbl 06599257
Summary: We consider two approaches for solving the classical minimum vertex coloring problem – that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors – namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

05C15 Coloring of graphs and hypergraphs
90C05 Linear programming
90C10 Integer programming
Full Text: DOI
[1] Apt K. R.Principles of Constraint Programming (2003) (Cambridge University Press, Cambridge, UK) CrossRef
[2] Barnier N., Brisset P.Graph coloring for air traffic flow management. Ann. Oper. Res. (2004) 130(1-4):163-178 · Zbl 1062.90011
[3] Brélaz D.New methods to color the vertices of a graph. Comm. ACM (1979) 22(4):251-256CrossRef
[4] Busygin S.A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. (2006) 154:2080-2096CrossRef · Zbl 1111.90020
[5] Capone A., Carello G., Filippini I., Gualandi S., Malucelli F.Solving a resource allocation problem in wireless mesh networks: A comparison between a CP-based and a classical column generation. Networks (2010) 55(3):221-233 · Zbl 1200.90038
[6] Coleman T. F., Moré J. J.Estimation of sparse Hessian matrices and graph coloring problems. Math. Programming (1984) 28(3):243-270 · Zbl 0572.65029
[7] Coll P., Marenco J., Méndez-Díaz I., Zabala P.Facets of the graph coloring polytope. Ann. Oper. Res. (2002) 116(1-4):79-90 · Zbl 1013.90097
[8] Demassey S., Pesant G., Rousseau L.-M.A cost-regular based hybrid column generation approach. Constraints (2006) 11(4):315-333CrossRef · Zbl 1117.90066
[9] Easton K., Nemhauser G. L., Trick M. A., Burke E., De Causmaecker P.Solving the travelling tournament problem: A combined integer programming and constraint programming approach. Proc. Practice Theory Automated Timetabling, Vol. 2740 (2002) (Springer, Berlin) 100-112Lecture Notes in Computer Science
[10] Fahle T., Möhring R., Raman R.Simple and fast: Improving a branch-and-bound algorithm for maximum clique. Proc. Ann. Eur. Symp. Algorithms., Vol. 2461 (2002) (Springer, Berlin) 47-86Lecture Notes in Computer Science
[11] Fahle T., Sellmann M.Cost based filtering for the constrained knapsack problem. Ann. Oper. Res. (2002) 115(1-4):73-93 · Zbl 1013.90105
[12] Fahle T., Junker U., Karisch S. E., Kohl N., Sellmann M., Vaaben B.Constraint programming based column generation for crew assignment. J. Heuristics (2002) 8(1):59-81 · Zbl 1073.90542
[13] Gabteni S., Grönkvist M., Beck J. C., Smith B. M.A hybrid column generation and constraint programming optimizer for the tail assignment problem. Proc. Integration AI OR Techniques CP Combin. Optim., Vol. 3990 (2006) (Springer, Berlin) 89-103Lecture Notes in Computer Science · Zbl 1177.90342
[14] Gendron B., Lebbah H., Pesant G., Barták R., Milano M.Improving the cooperation between the master problem and the subproblem in constraint programming based column generation. Proc. Integration AI OR Techniques CP Combin. Optim., Vol. 3524 (2005) (Springer, Berlin) 217-227Lecture Notes in Computer Science · Zbl 1133.68429
[15] Gent I. P., Petrie K. E., Puget J.-F., Rossi F., Van Beeck P., Walsh T.Symmetry in constraint programming. Handbook of Constraint Programming (2006) (Elsevier Science, Amsterdam) 329-376
[16] Gomes C. P., Selman B., Kautz H.Boosting combinatorial search through randomization. Proc. AAAI (1998) Madison, WI(John Wiley & Sons, New York) 431-437
[17] Grönkvist M., Régin J.-C., Rueher M.A constraint programming model for tail assignment. Proc. Integration AI OR Techniques CP Combin. Optim., Vol. 3011 (2004) (Springer, Berlin) 142-156Lecture Notes in Computer Science · Zbl 1094.68644
[18] Grönkvist M.Accelerating column generation for aircraft scheduling using constraint propagation. Comp. OR (2006) 33:2918-2934 · Zbl 1086.90023
[19] Gualandi S.Enhancing constraint programming-based column generation for integer programs. (2008) . Ph.D. thesis, Politecnico di Milano, Milano, Italy · Zbl 1180.90198
[20] Gualandi S., Malucelli F.A branching scheme for vertex coloring problems. (2009a) . Technical Report 2009-11-2450, Politecnico di Milano, Milano, Italy. http://www.optimization-online.org/DB_HTML/2009/11/2450.html · Zbl 1237.05075
[21] Gualandi S., Malucelli F.Constraint programming-based column generation. 4OR: Quart. J. Oper. Res. (2009b) 7(2):113-137 · Zbl 1175.90286
[22] Gvozdenović N., Laurent M.Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. SIAM J. Optim. (2008) 19(2):592-615CrossRef · Zbl 1213.05081
[23] Hansen J., Liden T., Barták R., Milano M.Group construction for airline cabin crew: Comparing constraint programming with branch and price. Proc. Integration AI OR Techniques CP Combin. Optim., Vol. 3524 (2005) (Springer, Berlin) 228-242Lecture Notes in Computer Science · Zbl 1133.90360
[24] Hansen P., Labbé M., Schindl D.Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discrete Optim. (2009) 6(2):135-147CrossRef · Zbl 1279.90115
[25] Harvey W. D., Ginsberg M. L., Mellish C. S.Limited discrepancy search. Proc. Internat. Joint Conf. Artificial Intelligence (1995) (Morgan Kaufmann, San Francisco) 607-615
[26] Hertz A., de Werra D.Using tabu search techniques for graph coloring. Computing (1987) 39(4):345-351 · Zbl 0626.68051
[27] Junker U., Karisch S. E., Kohl N., Vaaben B., Fahle T., Sellmann M., Jaffar J.A framework for constraint programming based column generation. Proc. Principles Practice of Constraint Programming, Vol. 1713 (1999) (Springer, Berlin) 261-274Lecture Notes in Computer Science · Zbl 0983.90059
[28] Leighton F. T.A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bureau Standards (1979) 84(6):489-506 · Zbl 0437.68021
[29] Lübbecke M. E., Desrosiers J.Selected topics in column generation. Oper. Res. (2005) 53(6):1007-1023Link · Zbl 1165.90578
[30] Malaguti E., Toth P.A survey on vertex coloring problems. Internat. Trans. Oper. Res. (2010) 17(1):1-34CrossRef · Zbl 1223.05079
[31] Mehrotra A., Trick M. A.A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8(4):344-354Link · Zbl 0884.90144
[32] Mehrotra A., Trick M. A.A branch-and-price approach for graph multi-coloring. Extending the Horizons: Advances in Computing, Optimization and Decision Technology (2007) (Springer, Berlin) 15-29 · Zbl 1241.90185
[33] Méndez-Díaz I., Zabala P.A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. (2006) 154(5):826-847CrossRef · Zbl 1120.90034
[34] Méndez-Díaz I., Zabala P.A cutting plane algorithm for graph coloring. Discrete Appl. Math. (2008) 156(2):159-179 · Zbl 1163.90012
[35] Milano M., Wallace M.Integrating operations research in constraint programming. 4OR: Quart. J. Oper. Res. (2006) 4(3):175-219 · Zbl 1125.90392
[36] Östergård P. R. J.A fast algorithm for the maximum clique problem. Discrete Appl. Math. (2002) 120(1-3):197-207CrossRef · Zbl 1019.05054
[37] Otten L., Grönkvist M., Dubhashi D. P., Benhamou F.Randomization in constraint programming for airline planning. Proc. Principles and Practice of Constraint Programming, Vol. 4204 (2006) (Springer, Berlin) 406-420Lecture Notes in Computer Science
[38] Pisinger D., Sigurd M.Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. (2007) 19(1):36-51Link · Zbl 1241.90118
[39] Prestwich S.Generalised graph colouring by a hybrid of local search and constraint programming. Discrete Appl. Math. (2008) 156(2):148-158 · Zbl 1179.90312
[40] Régin J. C.A filtering algorithm for constraints of difference in CSPs. Proc. Natl. Conf. Artificial Intelligence (1994) (American Association for Artificial Intelligence, Menlo Park, CA) 362-362
[41] Rossi F., Van Beek P., Walsh T.Handbook of Constraint Programming (2006) (Elsevier Science, Amsterdam)
[42] Rousseau L. M., Régin J.-C., Rueher M.Stabilization issues for constraint programming based column generation. Proc. Integration AI OR Techniques CP Combin. Optim., Vol. 3011 (2004) (Springer, Berlin) 402-408Lecture Notes in Computer Science · Zbl 1094.68655
[43] Rousseau L. M., Gendreau M., Pesant G., Focacci F.Solving VRPTWs with constraint programming based column generation. Ann. Oper. Res. (2004) 130:199-216CrossRef · Zbl 1062.90007
[44] Ryan D. M., Foster B. A., Wren A.An integer programming approach to scheduling. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (1981) (North-Holland, Amsterdam) 269-280
[45] Sadykov R., Wolsey L. A.Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates. INFORMS J. Comput. (2006) 18(2):209-217Abstract · Zbl 1241.90056
[46] Schrjiver A.Combinatorial Optimization–Polyhedra and Efficiency (2008) (Springer, New York)
[47] Schulte C., Lagerkvist M., Tack G.Modeling and Programming with Gecode (2009) . User’s manual, http://www.geocode.org
[48] Sellmann M., Zervoudakis K., Stamatopoulos P., Fahle T.Crew assignment via constraint programming: Integrating column generation and heuristic tree search. Ann. Oper. Res. (2002) 115:207-225 · Zbl 1013.90091
[49] Vanderbeck F.Branching in branch-and-price: A generic scheme. Math. Programming Ser. A (2011) 130(2):249-294CrossRef · Zbl 1229.90100
[50] Vasquez M.New results on the queens_n2 graph coloring problem. J. Heuristics (2004) 10(4):407-413
[51] Yunes T. H., Moura A. V., de Souza C. C.Solving very large crew scheduling problems to optimality. Proc. ACM Symp. Appl. Comput. (2000) (ACM, New York) 446-451
[52] Yunes T. H., Moura A. V., de Souza C. C.Hybrid column generation approaches for urban transit crew management problems. Transportation Sci. (2005) 39(2):273-288Link
[53] Zykov A. A.On some properties of linear complexes. Mat. Sbornik. (1949) 24(66):163-188
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.