Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
(2023) International Conference on Principles and Practice of Constraint Programming (CP)
Files
LIPIcsCP202325.pdf
Open Access - Adobe PDF
- 1.74 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, 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.
- Affiliations
Citations
Marty, T., François, T., Tessier, P., Gautier, L., Rousseau, L.-M., & Cappart, Q. (2023). Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver. Leibniz International Proceedings in Informatics, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), 25:1-25:19. https://hdl.handle.net/2078.5/272662 (Original work published 2023)