.png){kind=icon}
.png){kind=icon}
Return
Learning-Guided Adaptive Search Optimization for the Weighted Independent Set Problem
.png){kind=icon}
PRE
AI
J
J
X
P
DOI：10.59277/ROMJIST.2026.1.08.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The weighted independent set problem is a classic combinatorial optimization problem with broad applications. However, since practical applications require high solution quality, effectively balancing solution efficiency and quality remains a significant challenge. with an exact search, using heuristics to reduce the search space effectively. Based on the predicted probability, the solving process is divided into two stages. First, a graph neural network is used to predict the marginal probability of vertices belonging to the solution, and deep reinforcement learning trains a policy to construct a high-quality initial solution. Second, an adaptive search strategy is proposed, which dynamically defines a search range based on the credibility of the predicted probability. By reducing the size of the space that the exact solver needs to search, the solution time can be significantly decreased. The experimental results show that the proposed hybrid method improves the average solving speed by 86% while maintaining the same solution quality as the exact solver. Meanwhile, it demonstrates good scalability for large-scale graphs.
Keywords:
Combinatorial optimization
exact search
graph neural network
weight independent set
machine learning
Journal
R
IF:
3.9
Papers:
26
Citations:
442
Organization
Cited Papers