HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
This work addresses the computational bottleneck in solving large-scale ILPs, which is incremental as it builds on LNS methods to enhance efficiency for optimization tasks.
The paper tackles the slow solving of large-scale Integer Linear Programs (ILPs) by proposing HyP-ASO, a hybrid framework that combines a customized formula with deep Reinforcement Learning to improve neighborhood generation, resulting in significant performance gains over existing LNS-based approaches.
Directly solving large-scale Integer Linear Programs (ILPs) using traditional solvers is slow due to their NP-hard nature. While recent frameworks based on Large Neighborhood Search (LNS) can accelerate the solving process, their performance is often constrained by the difficulty in generating sufficiently effective neighborhoods. To address this challenge, we propose HyP-ASO, a hybrid policy-based adaptive search optimization framework that combines a customized formula with deep Reinforcement Learning (RL). The formula leverages feasible solutions to calculate the selection probabilities for each variable in the neighborhood generation process, and the RL policy network predicts the neighborhood size. Extensive experiments demonstrate that HyP-ASO significantly outperforms existing LNS-based approaches for large-scale ILPs. Additional experiments show it is lightweight and highly scalable, making it well-suited for solving large-scale ILPs.