{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:22:40Z","timestamp":1780633360592,"version":"3.54.1"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T00:00:00Z","timestamp":1732320000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T00:00:00Z","timestamp":1732320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the <jats:italic>branching heuristics<\/jats:italic>, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic <jats:italic>variable-selection heuristics<\/jats:italic> are available in the literature, the options for <jats:italic>value-selection heuristics<\/jats:italic> are more scarce. We propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a <jats:italic>deep Q-learning<\/jats:italic> algorithm, a tailored <jats:italic>reward signal<\/jats:italic>, and a <jats:italic>heterogeneous graph neural network<\/jats:italic>. Experiments on <jats:italic>graph coloring<\/jats:italic>, <jats:italic>maximum independent set<\/jats:italic>, <jats:italic>maximum cut<\/jats:italic>, and <jats:italic>minimum vertex cover<\/jats:italic> problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks. Additionally, we observe that fine-tuning a model with a different problem class can accelerate the learning process.<\/jats:p>","DOI":"10.1007\/s10601-024-09377-4","type":"journal-article","created":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T08:20:30Z","timestamp":1732350030000},"page":"234-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver"],"prefix":"10.1007","volume":"29","author":[{"given":"Tom","family":"Marty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L\u00e9o","family":"Boisvert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tristan","family":"Fran\u00e7ois","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Tessier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louis","family":"Gautier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louis-Martin","family":"Rousseau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8742-0774","authenticated-orcid":false,"given":"Quentin","family":"Cappart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,11,23]]},"reference":[{"key":"9377_CR1","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In: International Conference on Principles and Practice of Constraint Programming. Springer, pp. 529\u2013543.","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"9377_CR2","doi-asserted-by":"crossref","unstructured":"Refalo, P. (2004). Impact-based search strategies for constraint programming. In: International Conference on Principles and Practice of Constraint Programming. Springer, pp. 557\u2013571.","DOI":"10.1007\/978-3-540-30201-8_41"},{"key":"9377_CR3","doi-asserted-by":"crossref","unstructured":"Michel, L., & van Hentenryck, P. (2012). Activity-based search for black-box constraint programming solvers. In: International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming. Springer, pp. 228\u2013243.","DOI":"10.1007\/978-3-642-29828-8_15"},{"key":"9377_CR4","doi-asserted-by":"crossref","unstructured":"Fages, J. G., & Prud\u2019Homme, C. (2017). Making the first solution good! In: 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, pp. 1073\u20131077.","DOI":"10.1109\/ICTAI.2017.00164"},{"key":"9377_CR5","doi-asserted-by":"crossref","unstructured":"Cappart, Q., Moisan, T., Rousseau, L. M., & Pr\u00e9mont-Schwarz, I. (2021) Cire AA. Combining reinforcement learning and constraint programming for combinatorial optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol.\u00a035, pp. 3677\u20133687.","DOI":"10.1609\/aaai.v35i5.16484"},{"key":"9377_CR6","doi-asserted-by":"crossref","unstructured":"Doolaard, F., & Yorke-Smith, N. (2022). Online learning of variable ordering heuristics for constraint optimisation problems. Annals of Mathematics and Artificial Intelligence, pp. 1\u201330.","DOI":"10.1007\/s10472-022-09816-z"},{"key":"9377_CR7","doi-asserted-by":"crossref","unstructured":"Khalil, E. B., Bodic, P. L., Song, L., Nemhauser, G., & Dilkina, B. (2016). Learning to branch in Mixed Integer Programming. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 724\u2013731.","DOI":"10.1609\/aaai.v30i1.10080"},{"key":"9377_CR8","unstructured":"Gasse, M., Ch\u00e9telat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32."},{"key":"9377_CR9","first-page":"18087","volume":"33","author":"P Gupta","year":"2020","unstructured":"Gupta, P., Gasse, M., Khalil, E., Mudigonda, P., Lodi, A., & Bengio, Y. (2020). Hybrid models for learning to branch. Advances in neural information processing systems., 33, 18087\u201318097.","journal-title":"Advances in neural information processing systems."},{"issue":"4","key":"9377_CR10","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1287\/trsc.2021.1045","volume":"55","author":"M Morabit","year":"2021","unstructured":"Morabit, M., Desaulniers, G., & Lodi, A. (2021). Machine-learning-based column selection for column generation. Transportation Science., 55(4), 815\u2013831.","journal-title":"Transportation Science."},{"key":"9377_CR11","first-page":"9633","volume":"35","author":"C Chi","year":"2022","unstructured":"Chi, C., Aboussalah, A., Khalil, E., Wang, J., & Sherkat-Masoumi, Z. (2022). A deep reinforcement learning framework for column generation. Advances in Neural Information Processing Systems., 35, 9633\u20139644.","journal-title":"Advances in Neural Information Processing Systems."},{"issue":"5","key":"9377_CR12","doi-asserted-by":"publisher","first-page":"2552","DOI":"10.1287\/ijoc.2022.1194","volume":"34","author":"Q Cappart","year":"2022","unstructured":"Cappart, Q., Bergman, D., Rousseau, L. M., Pr\u00e9mont-Schwarz, I., & Parjadis, A. (2022). Improving variable orderings of approximate decision diagrams using reinforcement learning. INFORMS Journal on Computing., 34(5), 2552\u20132570.","journal-title":"INFORMS Journal on Computing."},{"key":"9377_CR13","doi-asserted-by":"crossref","unstructured":"Patel, R., & Khalil, E. B. (2023). LEO: Learning Efficient Orderings for Multiobjective Binary Decision Diagrams. arXiv preprint arXiv:2307.03171.","DOI":"10.1007\/978-3-031-60599-4_6"},{"key":"9377_CR14","doi-asserted-by":"crossref","unstructured":"Selsam, D., & Bj\u00f8rner, N. (2019). Guiding high-performance SAT solvers with unsat-core predictions. In: International Conference on Theory and Applications of Satisfiability Testing. Springer, pp. 336\u2013353.","DOI":"10.1007\/978-3-030-24258-9_24"},{"key":"9377_CR15","doi-asserted-by":"crossref","unstructured":"van Driel, R., Demirovi\u0107, E., & Yorke-Smith, N. (2021) Learning Variable Activity Initialisation for Lazy Clause Generation Solvers. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5\u20138, 2021, Proceedings 18. Springer, pp. 62\u201371.","DOI":"10.1007\/978-3-030-78230-6_4"},{"key":"9377_CR16","unstructured":"Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press."},{"issue":"2","key":"9377_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3054912","volume":"50","author":"A Hussein","year":"2017","unstructured":"Hussein, A., Gaber, M. M., Elyan, E., & Jayne, C. (2017). Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR)., 50(2), 1\u201335.","journal-title":"ACM Computing Surveys (CSUR)."},{"issue":"7553","key":"9377_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1038\/nature14539","volume":"521","author":"Y LeCun","year":"2015","unstructured":"LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature., 521(7553), 436\u2013444.","journal-title":"Nature."},{"key":"9377_CR19","first-page":"18514","volume":"35","author":"L Scavuzzo","year":"2022","unstructured":"Scavuzzo, L., Chen, F., Ch\u00e9telat, D., Gasse, M., Lodi, A., Yorke-Smith, N., et al. (2022). Learning to branch with tree MDPs. Advances in Neural Information Processing Systems., 35, 18514\u201318526.","journal-title":"Advances in Neural Information Processing Systems."},{"key":"9377_CR20","doi-asserted-by":"crossref","unstructured":"Song, W., Cao, Z., Zhang, J., Xu, C., & Lim, A. (2022). Learning variable ordering heuristics for solving Constraint Satisfaction Problems. Engineering Applications of Artificial Intelligence, 109, 104603.","DOI":"10.1016\/j.engappai.2021.104603"},{"issue":"1","key":"9377_CR21","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/JRPROC.1961.287775","volume":"49","author":"M Minsky","year":"1961","unstructured":"Minsky, M. (1961). Steps toward Artificial Intelligence. Proceedings of the IRE., 49(1), 8\u201330. https:\/\/doi.org\/10.1109\/JRPROC.1961.287775","journal-title":"Proceedings of the IRE."},{"key":"9377_CR22","doi-asserted-by":"crossref","unstructured":"Chalumeau, F., Coulon, I., Cappart, Q., & Rousseau, L. M. (2021). Seapearl: A constraint programming solver guided by reinforcement learning. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, pp. 392\u2013409.","DOI":"10.1007\/978-3-030-78230-6_25"},{"key":"9377_CR23","doi-asserted-by":"crossref","unstructured":"T\u00f6nshoff, J., Kisin, B., Lindner, J., & Grohe, M. (2023). One model, any CSP: graph neural networks as fast global search heuristics for constraint satisfaction. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 4280\u20134288.","DOI":"10.24963\/ijcai.2023\/476"},{"key":"9377_CR24","doi-asserted-by":"crossref","unstructured":"Boisvert, L., Verhaeghe, H., & Cappart, Q. (2024). Towards a Generic Representation of Cominatorial Problems for Learning-Based Approaches. arXiv preprint arXiv:2403.06026","DOI":"10.1007\/978-3-031-60597-0_7"},{"key":"9377_CR25","unstructured":"Marty, T., Fran\u00e7ois, T., Tessier, P., Gautier, L., Rousseau, L. M., & Cappart, Q. (2023). Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver. In: Yap, R. H. C. (ed.) 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). vol. 280 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 25:1\u201325:19."},{"issue":"2","key":"9377_CR26","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. European Journal of Operational Research., 290(2), 405\u2013421.","journal-title":"European Journal of Operational Research."},{"key":"9377_CR27","unstructured":"Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940"},{"key":"9377_CR28","unstructured":"Kool, W., van Hoof, H., & Welling, M. (2019) Attention, Learn to Solve Routing Problems! In: International Conference on Learning Representations."},{"key":"9377_CR29","doi-asserted-by":"crossref","unstructured":"Joshi, C. K., Cappart, Q., Rousseau, L. M., & Laurent, T. (2022). Learning the travelling salesperson problem requires rethinking generalization. Constraints, pp. 1\u201329.","DOI":"10.1007\/s10601-022-09327-y"},{"key":"9377_CR30","unstructured":"Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30."},{"issue":"4","key":"9377_CR31","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1038\/s42256-022-00468-6","volume":"4","author":"MJ Schuetz","year":"2022","unstructured":"Schuetz, M. J., Brubaker, J. K., & Katzgraber, H. G. (2022). Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence., 4(4), 367\u2013377.","journal-title":"Nature Machine Intelligence."},{"key":"9377_CR32","doi-asserted-by":"crossref","unstructured":"Bonami, P., Lodi, A., & Zarpellon, G. (2018). Learning a classification of mixed-integer quadratic programming problems. In: International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, pp. 595\u2013604.","DOI":"10.1007\/978-3-319-93031-2_43"},{"key":"9377_CR33","doi-asserted-by":"crossref","unstructured":"Kruber, M., L\u00fcbbecke, M. E., & Parmentier, A. (2017). Learning when to use a decomposition. In: International conference on AI and OR techniques in constraint programming for combinatorial optimization problems. Springer, pp. 202\u2013210.","DOI":"10.1007\/978-3-319-59776-8_16"},{"issue":"4","key":"9377_CR34","doi-asserted-by":"publisher","first-page":"3796","DOI":"10.1609\/aaai.v36i4.20294","volume":"36","author":"D Liu","year":"2022","unstructured":"Liu, D., Fischetti, M., & Lodi, A. (2022). Learning to Search in Local Branching. Proceedings of the AAAI Conference on Artificial Intelligence., 36(4), 3796\u2013380. https:\/\/doi.org\/10.1609\/aaai.v36i4.20294","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence."},{"key":"9377_CR35","doi-asserted-by":"crossref","unstructured":"Hoos, H. H. (2011). Automated algorithm configuration and parameter tuning. In: Autonomous Search. Springer, pp. 37\u201371.","DOI":"10.1007\/978-3-642-21434-9_3"},{"issue":"3","key":"9377_CR36","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF00126629","volume":"6","author":"JY Potvin","year":"1996","unstructured":"Potvin, J. Y., Dub\u00e9, D., & Robillard, C. (1996). A hybrid approach to vehicle routing using neural networks and genetic algorithms. Applied Intelligence., 6(3), 241\u2013252.","journal-title":"Applied Intelligence."},{"key":"9377_CR37","first-page":"32000","volume-title":"Advances in Neural Information Processing Systems","author":"AG Labassi","year":"2022","unstructured":"Labassi, A. G., Chetelat, D., & Lodi, A. (2022). Learning to Compare Nodes in Branch and Bound with Graph Neural Networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, & A. Oh (Eds.), Advances in Neural Information Processing Systems (Vol. 35, pp. 32000\u201332010). Curran Associates: Inc."},{"key":"9377_CR38","unstructured":"Nair V, Bartunov S, Gimeno F, Von\u00a0Glehn I, Lichocki P, & Lobov, I., et\u00a0al. (2020). Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349."},{"key":"9377_CR39","unstructured":"Sun, H., Chen, W., Li, H., & Song, L. (2020). Improving Learning to Branch via Reinforcement Learning. In: Learning Meets Combinatorial Algorithms at NeurIPS2020"},{"key":"9377_CR40","doi-asserted-by":"crossref","unstructured":"Parsonson, C. W., Laterre, A., & Barrett, T. D. (2023). Reinforcement learning for branch-and-bound optimisation using retrospective trajectories. In: Proceedings of the AAAI Conference on Artificial Intelligence, 37, 4061\u20134069.","DOI":"10.1609\/aaai.v37i4.25521"},{"key":"9377_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105400","volume":"134","author":"N Mazyavkina","year":"2021","unstructured":"Mazyavkina, N., Sviridov, S., Ivanov, S., & Burnaev, E. (2021). Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research., 134, 105400.","journal-title":"Computers & Operations Research."},{"key":"9377_CR42","doi-asserted-by":"crossref","unstructured":"van Hasselt, H., Guez, A., & Silver, D. (2016). Deep reinforcement learning with double Q-learning. In: Proceedings of the AAAI conference on artificial intelligence, 30","DOI":"10.1609\/aaai.v30i1.10295"},{"key":"9377_CR43","doi-asserted-by":"crossref","unstructured":"Xia, W., Yap, R. (2018). Learning robust search strategies using a bandit-based approach. In: Proceedings of the AAAI Conference on Artificial Intelligence, 32","DOI":"10.1609\/aaai.v32i1.12211"},{"key":"9377_CR44","unstructured":"Wattez, H., Koriche, F., Lecoutre, C., Paparrizou, A., & Tabary, S. (2020). Learning variable ordering heuristics with multi-armed bandits and restarts. In: ECAI 2020-24th European Conference on Artificial Intelligence"},{"key":"9377_CR45","doi-asserted-by":"crossref","unstructured":"Koriche, F., Lecoutre, C., Paparrizou, A., Wattez, H. (2022). Best Heuristic Identification for Constraint Satisfaction. In: 31st International Joint Conference on Artificial Intelligence (IJCAI\u201922). International Joint Conferences on Artificial Intelligence Organization pp. 1859\u20131865.","DOI":"10.24963\/ijcai.2022\/258"},{"key":"9377_CR46","doi-asserted-by":"crossref","unstructured":"Chu, G., & Stuckey, P. J. (2015). Learning value heuristics for constraint programming. In: textitInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2015. Springer, pp. 108\u2013123.","DOI":"10.1007\/978-3-319-18008-3_8"},{"key":"9377_CR47","unstructured":"Parjadis, A., Cappart, Q., Dilkina, B., Ferber, A., & Rousseau, L. M. (2024). Learning Lagrangian Multipliers for the Travelling Salesman Problem. In: Shaw, P. (ed.) 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). vol. 307 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik; pp. 22:1\u201322:18."},{"issue":"130","key":"9377_CR48","first-page":"1","volume":"24","author":"Q Cappart","year":"2023","unstructured":"Cappart, Q., Ch\u00e9telat, D., Khalil, E. B., Lodi, A., Morris, C., & Velickovic, P. (2023). Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research., 24(130), 1\u201361.","journal-title":"Journal of Machine Learning Research."},{"key":"9377_CR49","unstructured":"Schulman, J., Levine, S., Abbeel, P., Jordan, M., & Moritz, P. (2015). Trust region policy optimization. In: International conference on machine learning, pp. 1889\u20131897."},{"key":"9377_CR50","unstructured":"Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In: International conference on machine learning. PMLR, pp. 1861\u20131870."},{"key":"9377_CR51","unstructured":"Achiam, J. (2018). Spinning up in deep reinforcement learning."},{"key":"9377_CR52","doi-asserted-by":"crossref","unstructured":"Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., & Bellemare, M. G., et\u00a0al. (2015). Human-level control through deep reinforcement learning. Nature 18(7540), 529\u2013533.","DOI":"10.1038\/nature14236"},{"key":"9377_CR53","unstructured":"Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2015). Prioritized experience replay. arXiv preprint arXiv:1511.05952."},{"issue":"1","key":"9377_CR54","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1214\/aoms\/1177703732","volume":"35","author":"PJ Huber","year":"1964","unstructured":"Huber, P. J. (1964). Robust Estimation of a Location Parameter. The Annals of Mathematical Statistics., 35(1), 73\u201310. https:\/\/doi.org\/10.1214\/aoms\/1177703732","journal-title":"The Annals of Mathematical Statistics."},{"issue":"1","key":"9377_CR55","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF00115009","volume":"3","author":"RS Sutton","year":"1988","unstructured":"Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning., 3(1), 9\u20134. https:\/\/doi.org\/10.1007\/BF00115009","journal-title":"Machine Learning."},{"issue":"1","key":"9377_CR56","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","volume":"20","author":"F Scarselli","year":"2008","unstructured":"Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2008). The graph neural network model. IEEE transactions on neural networks., 20(1), 61\u201380.","journal-title":"IEEE transactions on neural networks."},{"key":"9377_CR57","unstructured":"Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. In: International conference on machine learning. PMLR, pp. 1263\u20131272."},{"key":"9377_CR58","unstructured":"Glorot, X., Bordes, A., Bengio, Y. (2011). Deep sparse rectifier neural networks. In: Proceedings of the fourteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, pp. 315\u2013323."},{"key":"9377_CR59","unstructured":"Kingma, D., P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980."},{"key":"9377_CR60","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s12532-020-00190-7","volume":"13","author":"L Michel","year":"2021","unstructured":"Michel, L., Schaus, P., & van Hentenryck, P. (2021). MiniCP: a lightweight solver for constraint programming. Mathematical Programming Computation., 13, 133\u2013184.","journal-title":"Mathematical Programming Computation."},{"issue":"2","key":"9377_CR61","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E. D., & Mor\u00e9, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming., 91(2), 201\u2013213.","journal-title":"Mathematical programming."},{"issue":"1","key":"9377_CR62","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., & Barab\u00e1si, A. L. (2002). Statistical mechanics of complex networks. Reviews of modern physics., 74(1), 47.","journal-title":"Reviews of modern physics."},{"key":"9377_CR63","unstructured":"Trott, A., Zheng, S., Xiong, C., Socher, R. (2019). Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards. Advances in Neural Information Processing Systems, 32."},{"key":"9377_CR64","unstructured":"Maas, A. L., Hannun, A.Y., & Ng, A. Y., et\u00a0al. (2013). Rectifier nonlinearities improve neural network acoustic models. In: Proc. icml. vol.\u00a030. Atlanta, Georgia, USA, p.\u00a03."},{"key":"9377_CR65","doi-asserted-by":"crossref","unstructured":"He, K., Zhang, X., Ren, S., Sun, J. (2016). Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770\u2013778.","DOI":"10.1109\/CVPR.2016.90"},{"key":"9377_CR66","unstructured":"Harvey, W. D., & Ginsberg, M. L. (1995). Limited discrepancy search. In: Proceedings of the 14th international joint conference on Artificial intelligence, vol.\u00a01, pp. 607\u2013613."},{"key":"9377_CR67","unstructured":"Yu, X., Serra, T., Ramalingam, S., & Zhe, S. (2022). The combinatorial brain surgeon: Pruning weights that cancel one another in neural networks. In: International Conference on Machine Learning. PMLR, pp. 25668\u201325683."},{"issue":"1","key":"9377_CR68","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1287\/ijoc.2015.0648","volume":"28","author":"D Bergman","year":"2016","unstructured":"Bergman, D., Cire, A. A., van Hoeve, W. J., & Hooker, J. N. (2016). Discrete optimization with decision diagrams. INFORMS Journal on Computing., 28(1), 47\u201366.","journal-title":"INFORMS Journal on Computing."},{"key":"9377_CR69","unstructured":"Wang, Y., Hu, X., Xie, J., Yin, Z., Zhou, Y., & Huang, X., et\u00a0al. (2023). Graph Structure Learning via Lottery Hypothesis at Scale. Proceedings of Machine Learning Research, 2023(222)."},{"key":"9377_CR70","doi-asserted-by":"crossref","unstructured":"Campeotto, F., Dal\u00a0Palu, A., Dovier, A., Fioretto, F., Pontelli, E. (2014). Exploring the use of GPUs in constraint solving. In: Practical Aspects of Declarative Languages: 16th International Symposium, PADL 2014, San Diego, CA, USA, January 20\u201321, 2014. Proceedings 16. Springer, pp. 152\u2013167.","DOI":"10.1007\/978-3-319-04132-2_11"},{"key":"9377_CR71","unstructured":"Tardivo, F., Dovier, A. (2022). Constraints propagation on GPU: A case study for AllDifferent. In: Proceedings of the 37th Italian Conference on Computational Logic"},{"key":"9377_CR72","doi-asserted-by":"crossref","unstructured":"Tardivo, F., Dovier, A., Formisano, A., Michel, L., Pontelli, E. (2023). Constraint Propagation on GPU: A Case Study for the Cumulative Constraint. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, pp. 336\u2013353.","DOI":"10.1007\/978-3-031-33271-5_22"},{"key":"9377_CR73","unstructured":"Sunehag, P., Lever, G., Gruslys , A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et\u00a0al. (2018). Value-decomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th international conference on autonomous agents and multi-agent systems (pp. 2085\u20132087)."},{"key":"9377_CR74","unstructured":"Garg, V., Jegelka, S., & Jaakkola, T. (2020). Generalization and representational limits of graph neural networks. In: International Conference on Machine Learning. PMLR, pp. 3419\u20133430."},{"key":"9377_CR75","doi-asserted-by":"crossref","unstructured":"Tinn, R., Cheng, H., Gu, Y., Usuyama, N., Liu, X., & Naumann, T., et\u00a0al. (2023). Fine-tuning large neural language models for biomedical natural language processing. Patterns, 4(4).","DOI":"10.1016\/j.patter.2023.100729"},{"issue":"3","key":"9377_CR76","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1038\/s42256-023-00626-4","volume":"5","author":"N Ding","year":"2023","unstructured":"Ding, N., Qin, Y., Yang, G., Wei, F., Yang, Z., Su, Y., et al. (2023). Parameter-efficient fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence., 5(3), 220\u2013235.","journal-title":"Nature Machine Intelligence."},{"key":"9377_CR77","doi-asserted-by":"crossref","unstructured":"Sun, Y., Zhu, Q., Yang, Y., Wang, C., Fan, T., & Zhu, J., et\u00a0al. (2024). Fine-Tuning Graph Neural Networks by Preserving Graph Generative Patterns. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a038, pp. 9053\u20139061.","DOI":"10.1609\/aaai.v38i8.28755"},{"key":"9377_CR78","doi-asserted-by":"crossref","unstructured":"Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., & Rattan, G., et\u00a0al. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. In: Proceedings of the AAAI conference on artificial intelligence. vol.\u00a033, pp. 4602\u20134609.","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"9377_CR79","doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Rattan, G., & Verbitsky, O. (2015). On the power of color refinement. In: Fundamentals of Computation Theory: 20th International Symposium, FCT 2015, Gda\u0144sk, Poland, August 17\u201319, 2015, Proceedings 20. Springer, pp. 339\u2013350.","DOI":"10.1007\/978-3-319-22177-9_26"},{"key":"9377_CR80","unstructured":"Chen, Z., Liu, J., Chen, X., Wang. X., & Yin, W. (2024). Rethinking the Capacity of Graph Neural Networks for Branching Strategy. arXiv preprint arXiv:2402.07099."},{"key":"9377_CR81","unstructured":"Audemard, G., Lecoutre, C., & Lonca, E. (2022). Proceedings of the 2022 XCSP3 Competition. arXiv preprint arXiv:2209.00917."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-024-09377-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-024-09377-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-024-09377-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T12:21:10Z","timestamp":1737375670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-024-09377-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,23]]},"references-count":81,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9377"],"URL":"https:\/\/doi.org\/10.1007\/s10601-024-09377-4","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,23]]},"assertion":[{"value":"13 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We declare the following conflicts of interest with the editorial board: prof. Pesant (same institution), prof. Bergman (previous co-author), prof. Van Hoeve (previous co-author), prof. Rousseau (author of the submitted paper), and prof. Cappart (author of the submitted paper).","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interests"}}]}}