Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
Constraint programming is known for being an efficient approach for solving combinatorial problems. Important design choices in a solver are the branching heuristics, which are 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. To the best of our knowledge, it is still an open research question. Although several generic variable-selection heuristics are available in the literature, the options for a generic value-selection heuristic are more scarce. In this paper, 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 architecture. Experiments on graph coloring, maximum independent set, and maximum cut problems show that our framework is able to find better solutions close to optimality without requiring a large amounts of backtracks while being generic.
Code (1)
Tasks
Graph Neural NetworkQ-LearningVariable SelectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based se…
SchedulingConditional Gumbel-Softmax for constrained feature selection with application to node selection in wireless sensor networks
In this paper, we introduce Conditional Gumbel-Softmax as a method to perform end-to-end learning of the optimal feature subset for a given task and deep neural network (DNN) model, while adhering to certain pairwise con…
EEGfeature selectionLearning Local Search Heuristics for Boolean Satisfiability
We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act…
Deep Reinforcement LearningGraph Neural Networkreinforcement-learningReinforcement Learning+2LLM-Driven Reasoning for Constraint-Aware Feature Selection in Industrial Systems
Feature selection is a crucial step in large-scale industrial machine learning systems, directly affecting model accuracy, efficiency, and maintainability. Traditional feature selection methods rely on labeled data and s…
Model Correlation Detection via Random Selection Probing
The growing prevalence of large language models (LLMs) and vision-language models (VLMs) has heightened the need for reliable techniques to determine whether a model has been fine-tuned from or is even identical to anoth…