{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:18:45Z","timestamp":1743056325031,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642213106"},{"type":"electronic","value":"9783642213113"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21311-3_11","type":"book-chapter","created":{"date-parts":[[2011,5,5]],"date-time":"2011-05-05T08:47:22Z","timestamp":1304585242000},"page":"99-116","source":"Crossref","is-referenced-by-count":6,"title":["Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry"],"prefix":"10.1007","author":[{"given":"Tim","family":"Januschowski","sequence":"first","affiliation":[]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Second DIMACS implementation challenge: Maximum clique, graph coloring, and satisfiability (1993), \n                    ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/benchmarks\/clique\/"},{"key":"11_CR2","unstructured":"COLOR 2002 \u2013 computational symposium: Graph coloring and its generalizations (2002), \n                    http:\/\/mat.gsia.cmu.edu\/COLOR02"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.disopt.2006.10.006","volume":"4","author":"T. Achterberg","year":"2007","unstructured":"Achterberg, T.: Conflict analysis in mixed integer programming. Discrete Optimization\u00a04(1), 4\u201320 (2007)","journal-title":"Discrete Optimization"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Achterberg, T.: SCIP: Solving constraint integer programs. Mathematical Programming Computation\u00a01(1) (2009)","DOI":"10.1007\/s12532-008-0001-1"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-01929-6_23","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"T. Achterberg","year":"2009","unstructured":"Achterberg, T., Berthold, T.: Hybrid branching. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol.\u00a05547, pp. 309\u2013311. Springer, Heidelberg (2009)"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/978-3-540-68155-7_4","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"T. Achterberg","year":"2008","unstructured":"Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: A new approach to integrate CP and MIP. In: Trick, M.A. (ed.) CPAIOR 2008. LNCS, vol.\u00a05015, pp. 6\u201320. Springer, Heidelberg (2008)"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-642-00142-0_70","volume-title":"Operations Research Proceedings 2008","author":"T. Berthold","year":"2009","unstructured":"Berthold, T., Pfetsch, M.E.: Detecting orbitopal symmetries. In: Operations Research Proceedings 2008, pp. 433\u2013438. Springer, Heidelberg (2009)"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10601-006-8059-8","volume":"11","author":"D. Cohen","year":"2006","unstructured":"Cohen, D., Jeavons, P., Jefferson, C., Petrie, K., Smith, B.: Symmetry definitions for constraint satisfaction problems. Constraints\u00a011, 115\u2013137 (2006)","journal-title":"Constraints"},{"key":"11_CR9","first-page":"148","volume-title":"Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR 1996)","author":"J. Crawford","year":"1996","unstructured":"Crawford, J., Ginsberg, M., Luks, E., Roy, A.: Symmetry-breaking predicates for search problems. In: Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR 1996), pp. 148\u2013159. Morgan Kaufmann, San Francisco (1996)"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-46135-3_31","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"P. Flener","year":"2002","unstructured":"Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking row and column symmetries in matrix models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 462\u2013476. Springer, Heidelberg (2002)"},{"issue":"1","key":"11_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10472-009-9172-3","volume":"57","author":"P. Flener","year":"2009","unstructured":"Flener, P., Pearson, J., Sellmann, M.: Static and dynamic structural symmetry breaking. Annals of Mathematics and Artificial Intelligence\u00a057(1), 37\u201357 (2009)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM\u00a056:25:1\u201325:32 (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1016\/j.artint.2006.03.002","volume":"170","author":"A.M. Frisch","year":"2006","unstructured":"Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence\u00a0170, 803\u2013834 (2006)","journal-title":"Artificial Intelligence"},{"key":"11_CR14","first-page":"239","volume":"6","author":"R. Frucht","year":"1938","unstructured":"Frucht, R.: Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Mathematica\u00a06, 239\u2013250 (1938)","journal-title":"Compositio Mathematica"},{"key":"11_CR15","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S1574-6526(06)80014-3","volume-title":"Handbook of Constraint Programming","author":"I.P. Gent","year":"2006","unstructured":"Gent, I.P., Petrie, K.E., Puget, J.-F.: Symmetry in constraint programming. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 329\u2013376. Elsevier, Amsterdam (2006)"},{"key":"11_CR17","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, 2nd edn. Algorithms and Combinatorics, vol.\u00a02. Springer, Heidelberg (1993)","edition":"2"},{"key":"11_CR18","unstructured":"Januschowski, T., Pfetsch, M.E.: The maximal k-colorable subgraph problem and orbitopes (2010) (preprint), \n                    http:\/\/www.optimization-online.org\/DB_HTML\/2010\/11\/2821.html"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Januschowski, T., Pfetsch, M.E.: Branch-cut-and-propagate for the maximum k-colorable subgraph problem (2011) (preprint), \n                    http:\/\/www.optimization-online.org\/DB_HTML\/2011\/02\/2909.html","DOI":"10.1007\/978-3-642-21311-3_11"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/0196-6774(82)90032-3","volume":"3","author":"D.S. Johnson","year":"1982","unstructured":"Johnson, D.S.: The NP-completeness column: An ongoing guide. V. Journal of Algorithms\u00a03, 381\u2013395 (1982)","journal-title":"Journal of Algorithms"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-540-72792-7_7","volume-title":"Integer Programming and Combinatorial Optimization","author":"V. Kaibel","year":"2007","unstructured":"Kaibel, V., Peinhardt, M., Pfetsch, M.E.: Orbitopal fixing. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 74\u201388. Springer, Heidelberg (2007)"},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-006-0081-5","volume":"114","author":"V. Kaibel","year":"2008","unstructured":"Kaibel, V., Pfetsch, M.E.: Packing and partitioning orbitopes. Mathematical Programming\u00a0114(1), 1\u201336 (2008)","journal-title":"Mathematical Programming"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-642-15396-9_26","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2010","author":"G. Katsirelos","year":"2010","unstructured":"Katsirelos, G., Narodytska, N., Walsh, T.: On the complexity and completeness of static constraints for breaking row and column symmetry. In: Cohen, D. (ed.) CP 2010. LNCS, vol.\u00a06308, pp. 305\u2013320. Springer, Heidelberg (2010)"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Koster, A.M.C.A., Ruepp, S.: Benchmarking RWA strategies for dynamically controlled optical networks. In: Proceedings of the Thirteenth International Telecommunications Network Strategy and Planning Symposium (NETWORKS 2008), pp. 1\u201314 (2008)","DOI":"10.1109\/NETWKS.2008.6231329"},{"key":"11_CR25","unstructured":"Koster, A.M.C.A., Scheffel, M.: A routing and network dimensioning strategy to reduce wavelength continuity conflicts in all-optical networks. In: Proceedings of the International Network Optimization Conference (INOC 2007), Spa, Belgium (2007)"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-540-72792-7_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"J. Linderoth","year":"2007","unstructured":"Linderoth, J., Ostrowski, J.P., Rossi, F., Smriglio, S.: Orbital branching. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 104\u2013118. Springer, Heidelberg (2007)"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-24838-5_24","volume-title":"Experimental and Efficient Algorithms","author":"C. Lucet","year":"2004","unstructured":"Lucet, C., Mendes, F., Moukrim, A.: Pre-processing and linear-decomposition algorithm to solve the k-colorability problem. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol.\u00a03059, pp. 315\u2013325. Springer, Heidelberg (2004)"},{"issue":"1","key":"11_CR28","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-002-0358-2","volume":"94","author":"F. Margot","year":"2002","unstructured":"Margot, F.: Pruning by isomorphism in branch-and-cut. Mathematical Programming\u00a094(1), 71\u201390 (2002)","journal-title":"Mathematical Programming"},{"issue":"2-3","key":"11_CR29","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-002-0316-z","volume":"94","author":"F. Margot","year":"2003","unstructured":"Margot, F.: Small covering designs by branch-and-cut. Mathematical Programming\u00a094(2-3), 207\u2013220 (2003)","journal-title":"Mathematical Programming"},{"issue":"1","key":"11_CR30","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.disopt.2006.10.008","volume":"4","author":"F. Margot","year":"2007","unstructured":"Margot, F.: Symmetric ILP: Coloring and small integers. Discrete Optimization\u00a04(1), 40\u201362 (2007)","journal-title":"Discrete Optimization"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/978-3-540-68279-0_17","volume-title":"50 Years of Integer Programming 1958\u20132008","author":"F. Margot","year":"2010","unstructured":"Margot, F.: Symmetry in integer linear programming. In: J\u00fcnger, M., Liebling, T., Naddef, D., Nemhauser, G.L., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming 1958\u20132008, ch. 17, pp. 647\u2013681. Springer, Heidelberg (2010)"},{"key":"11_CR32","unstructured":"McKay, B.D.: Practical graph isomorphism. In: Congressus Numerantium, pp. 45\u201387 (1981)"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S1571-0653(04)00254-9","volume":"7","author":"I. M\u00e9ndez-D\u00edaz","year":"2001","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A polyhedral approach for graph coloring. Electronic Notes in Discrete Mathematics\u00a07, 178\u2013181 (2001)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"5","key":"11_CR34","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"I. M\u00e9ndez-D\u00edaz","year":"2006","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics\u00a0154(5), 826\u2013847 (2006)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"11_CR35","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.dam.2006.07.010","volume":"156","author":"I. M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A cutting plane algorithm for graph coloring. Discrete Applied Mathematics\u00a0156(2), 159\u2013179 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR36","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and combinatorial optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. Wiley-Interscience, New York (1988)"},{"issue":"1","key":"11_CR37","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s10107-009-0273-x","volume":"126","author":"J. Ostrowski","year":"2011","unstructured":"Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Mathematical Programming\u00a0126(1), 147\u2013178 (2011)","journal-title":"Mathematical Programming"},{"key":"11_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-56804-2_33","volume-title":"Methodologies for Intelligent Systems","author":"J.-F. Puget","year":"1993","unstructured":"Puget, J.-F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Komorowski, J., Ra\u015b, Z.W. (eds.) ISMIS 1993. LNCS, vol.\u00a0689, pp. 350\u2013361. Springer, Heidelberg (1993)"},{"key":"11_CR39","unstructured":"SCIP. Solving Constraint Integer Programs, \n                    http:\/\/scip.zib.de"},{"key":"11_CR40","series-title":"Ser. Discrete Math. Theor. Comput. Sci.","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1090\/dimacs\/026\/17","volume-title":"Cliques, Coloring, and Satisfiability. Second DIMACS Implementation Challenge. Proceedings of a Workshop held at DIMACS, 1993","author":"E.C. Sewell","year":"1996","unstructured":"Sewell, E.C.: An improved algorithm for exact graph coloring. In: Johnson, D.S., Trick, M. (eds.) Cliques, Coloring, and Satisfiability. Second DIMACS Implementation Challenge. Proceedings of a Workshop held at DIMACS, 1993. Ser. Discrete Math. Theor. Comput. Sci., vol.\u00a026, pp. 359\u2013373. AMS, DIMACS (1996)"}],"container-title":["Lecture Notes in Computer Science","Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21311-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T01:03:21Z","timestamp":1609203801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21311-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642213106","9783642213113"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21311-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}