Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver

Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the <i>branching heuristics</i>, 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 <i>variable-selection heuristics</i> are available in the literature, the options for <i>value-selection heuristics</i> 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 <i>deep Q-learning</i> algorithm, a tailored <i>reward signal</i>, and a <i>heterogeneous graph neural network</i>. Experiments on <i>graph coloring</i>, <i>maximum independent set</i>, <i>maximum cut</i>, and <i>minimum vertex cover</i> 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.