Learning Branching Heuristics from Graph Neural Networks
Backtracking has been widely used for solving problems in artificial intelligence (AI), including constraint satisfaction problems and combinatorial optimization problems. Good branching heuristics can efficiently improve the performance of backtracking by helping prune the search space and leading the search to the most promising direction. In this paper, we first propose a new graph neural network (GNN) model designed using the probabilistic method. From the GNN model, we introduce an approach to learn a branching heuristic for combinatorial optimization problems. In particular, our GNN model learns appropriate probability distributions on vertices in given graphs from which the branching heuristic is extracted and used in a backtracking search. Our experimental results for the (minimum) dominating-clique problem show that this learned branching heuristic performs better than the minimum-remaining-values heuristic in terms of the number of branches of the whole search tree. Our approach introduces a new way of applying GNNs towards enhancing the classical backtracking algorithm used in AI.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationGraph Neural NetworkMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Neural heuristics for SAT solving
We use neural graph networks with a message-passing architecture and an attention mechanism to enhance the branching heuristic in two SAT-solving algorithms. We report improvements of learned neural heuristics compared w…
Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?
We present Graph-Q-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-Q-SAT are complete S…
Feature EngineeringQ-LearningReinforcement Learning (RL)Can $Q$-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?
We present Graph-$Q$-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-$Q$-SAT are comple…
Feature EngineeringQ-LearningReinforcement LearningReinforcement Learning (RL)Learning to Rank the Initial Branching Order of SAT Solvers
Finding good branching orders is key to solving SAT problems efficiently, but finding such branching orders is a difficult problem. Using a learning based approach to predict a good branching order before solving, theref…
Graph Neural NetworkBranching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality
Graph Neural Networks (GNNs) have emerged as a promising approach for ``learning to branch'' in Mixed-Integer Linear Programming (MILP). While standard Message-Passing GNNs (MPNNs) are efficient, they theoretically lack …