Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

References

• Apt K. R.Principles of Constraint Programming (2003) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Barnier N., Brisset P. Graph coloring for air traffic flow management. Ann. Oper. Res. (2004) 130(1–4):163–178Crossref, Google Scholar
• Brélaz D. New methods to color the vertices of a graph. Comm. ACM (1979) 22(4):251–256Crossref, Google Scholar
• Busygin S. A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. (2006) 154:2080–2096Crossref, Google Scholar
• 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–233Crossref, Google Scholar
• Coleman T. F., Moré J. J. Estimation of sparse Hessian matrices and graph coloring problems. Math. Programming (1984) 28(3):243–270Crossref, Google Scholar
• 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–90Crossref, Google Scholar
• Demassey S., Pesant G., Rousseau L.-M. A cost-regular based hybrid column generation approach. Constraints (2006) 11(4):315–333Crossref, Google Scholar
• 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 ScienceGoogle Scholar
• 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 ScienceCrossref, Google Scholar
• Fahle T., Sellmann M. Cost based filtering for the constrained knapsack problem. Ann. Oper. Res. (2002) 115(1–4):73–93Crossref, Google Scholar
• 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–81Crossref, Google Scholar
• 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 ScienceCrossref, Google Scholar
• 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 ScienceCrossref, Google Scholar
• 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–376Crossref, Google Scholar
• Gomes C. P., Selman B., Kautz H. Boosting combinatorial search through randomization. Proc. AAAI (1998) Madison, WI(John Wiley & Sons, New York) 431–437Google Scholar
• 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 ScienceCrossref, Google Scholar
• Grönkvist M. Accelerating column generation for aircraft scheduling using constraint propagation. Comp. OR (2006) 33:2918–2934Crossref, Google Scholar
• Gualandi S. Enhancing constraint programming-based column generation for integer programs. (2008) . Ph.D. thesis, Politecnico di Milano, Milano, ItalyGoogle Scholar
• 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.htmlGoogle Scholar
• Gualandi S., Malucelli F. Constraint programming-based column generation. 4OR: Quart. J. Oper. Res. (2009b) 7(2):113–137Crossref, Google Scholar
• 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, Google Scholar
• 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 ScienceCrossref, Google Scholar
• 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, Google Scholar
• Harvey W. D., Ginsberg M. L., Mellish C. S. Limited discrepancy search. Proc. Internat. Joint Conf. Artificial Intelligence (1995) (Morgan Kaufmann, San Francisco) 607–615Google Scholar
• Hertz A., de Werra D. Using tabu search techniques for graph coloring. Computing (1987) 39(4):345–351Crossref, Google Scholar
• 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 ScienceCrossref, Google Scholar
• Leighton F. T. A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bureau Standards (1979) 84(6):489–506Crossref, Google Scholar
• Lübbecke M. E., Desrosiers J. Selected topics in column generation. Oper. Res. (2005) 53(6):1007–1023Link, Google Scholar
• Malaguti E., Toth P. A survey on vertex coloring problems. Internat. Trans. Oper. Res. (2010) 17(1):1–34Crossref, Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8(4):344–354Link, Google Scholar
• 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–29Crossref, Google Scholar
• Méndez-Díaz I., Zabala P. A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. (2006) 154(5):826–847Crossref, Google Scholar
• Méndez-Díaz I., Zabala P. A cutting plane algorithm for graph coloring. Discrete Appl. Math. (2008) 156(2):159–179Crossref, Google Scholar
• Milano M., Wallace M. Integrating operations research in constraint programming. 4OR: Quart. J. Oper. Res. (2006) 4(3):175–219Crossref, Google Scholar
• Östergård P. R. J. A fast algorithm for the maximum clique problem. Discrete Appl. Math. (2002) 120(1–3):197–207Crossref, Google Scholar
• 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 ScienceCrossref, Google Scholar
• 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, Google Scholar
• Prestwich S. Generalised graph colouring by a hybrid of local search and constraint programming. Discrete Appl. Math. (2008) 156(2):148–158Crossref, Google Scholar
• 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–362Google Scholar
• Rossi F., Van Beek P., Walsh T.Handbook of Constraint Programming (2006) (Elsevier Science, Amsterdam) Google Scholar
• 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 ScienceCrossref, Google Scholar
• Rousseau L. M., Gendreau M., Pesant G., Focacci F. Solving VRPTWs with constraint programming based column generation. Ann. Oper. Res. (2004) 130:199–216Crossref, Google Scholar
• 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–280Google Scholar
• 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–217Link, Google Scholar
• Schrjiver A.Combinatorial Optimization—Polyhedra and Efficiency (2008) (Springer, New York) Google Scholar
• Schulte C., Lagerkvist M., Tack G.Modeling and Programming with Gecode (2009) . User's manual, http://www.geocode.orgGoogle Scholar
• 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–225Crossref, Google Scholar
• Vanderbeck F. Branching in branch-and-price: A generic scheme. Math. Programming Ser. A (2011) 130(2):249–294Crossref, Google Scholar
• Vasquez M. New results on the queens_n2 graph coloring problem. J. Heuristics (2004) 10(4):407–413Crossref, Google Scholar
• 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–451Crossref, Google Scholar
• 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, Google Scholar
• Zykov A. A. On some properties of linear complexes. Mat. Sbornik. (1949) 24(66):163–188Google Scholar