2026-07-20T05:44:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19062 2024-03-12T12:01:37Z ddc:004 open_access

Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver Marty, Tom François, Tristan Tessier, Pierre Gautier, Louis Rousseau, Louis-Martin Cappart, Quentin Branching heuristic Deep reinforcement learning Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, 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 variable-selection heuristics are available in the literature, the options for value-selection heuristics 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 deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network. Experiments on graph coloring, maximum independent set, and maximum cut 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tom Marty and Tristan François and Pierre Tessier and Louis Gautier and Louis-Martin Rousseau and Quentin Cappart 2023 Is Part Of LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2023.25 urn:nbn:de:0030-drops-190625 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode