Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver
(2024) Constraints : an international journal — Vol. 29, n° 3-4, p. 234-260 (2024)
Files
s10601-024-09377-4.pdf
Open Access - Adobe PDF
- 1.67 MB
Details
- Authors
- Abstract
- 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, maximum cut, and minimum vertex cover 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.
- Affiliations
Citations
Marty, T., Boisvert, L., François, T., Tessier, P., Gautier, L., Rousseau, L.-M., & Cappart, Q. (2024). Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver. Constraints : an international journal, 29(3-4), 234-260. https://doi.org/10.1007/s10601-024-09377-4 (Original work published 2024)