Learning-Guided Adaptive Search Optimization for the Weighted Independent Set Problem

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.