ROMJIST Volume 29, No. 1, 2026, pp. 89-99, DOI: 10.59277/ROMJIST.2026.1.08
Caixia CHEN, Jie WU, Jie CHEN, Yu XIA, Radu-Emil PRECUP Learning-Guided Adaptive Search Optimization for the Weighted Independent Set Problem
ABSTRACT: 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. This paper proposes a new hybrid solution method that combines neural network heuristics 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.Read full text (pdf)