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

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Constraint programming (CP) is effective for combinatorial problems, with branching heuristics crucial for solver efficiency.
• Developing specialized heuristics requires significant time and problem-specific expertise.
• Existing generic variable-selection heuristics are more numerous than value-selection heuristics.

Purpose of the Study:

• To develop a generic machine learning procedure for automatically learning value-selection heuristics in CP solvers.
• To address the scarcity of automated methods for value-selection heuristic generation.

Main Methods:

• Employed a deep Q-learning algorithm combined with a tailored reward signal.
• Utilized a heterogeneous graph neural network for learning the heuristic.
• Tested the framework on graph coloring, maximum independent set, maximum cut, and minimum vertex cover problems.

Main Results:

• The learned value-selection heuristic demonstrates competitive performance against established impact-based and activity-based heuristics.
• The framework successfully finds near-optimal solutions with minimal backtracking.
• Fine-tuning the model on different problem classes accelerates the learning process.

Conclusions:

• The proposed deep Q-learning framework offers an effective, automated approach to generating value-selection heuristics for CP.
• This method reduces reliance on expert knowledge and enhances solver performance across various combinatorial problems.
• Transfer learning through fine-tuning shows promise for faster adaptation to new problem domains.