Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
Sunehag, Peter, Guy Lever, Gruslys, Audrunas et al. · arXiv (Cornell University) · 2017
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.
Cited by 491 works. doi:10.4230/lipics.cp.2023.25 Open-access PDF
Authors
References
- Adam: A Method for Stochastic Optimization
- Markov Decision Processes: Discrete Stochastic Dynamic Programming.
- Reinforcement Learning
- Markov games as a framework for multi-agent reinforcement learning
- Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping
- A Comprehensive Survey of Multiagent Reinforcement Learning
- Dueling Network Architectures for Deep Reinforcement Learning
- Cooperative Multi-Agent Learning: The State of the Art
- Learning to Communicate with Deep Multi-Agent Reinforcement Learning
- Algorithms for Reinforcement Learning