HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Xu, Ning, Zhang, Junkai, Wu, Yang, Ye, Huigen, Xu, Hua, Xu, Huiling, Zhang, Yifan
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

_version_	1866916959742853120
author	Xu, Ning Zhang, Junkai Wu, Yang Ye, Huigen Xu, Hua Xu, Huiling Zhang, Yifan
author_facet	Xu, Ning Zhang, Junkai Wu, Yang Ye, Huigen Xu, Hua Xu, Huiling Zhang, Yifan
contents	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.
format	Preprint
id	arxiv_https___arxiv_org_abs_2509_15828
institution	arXiv
publishDate	2025
record_format	arxiv
spellingShingle	HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs Xu, Ning Zhang, Junkai Wu, Yang Ye, Huigen Xu, Hua Xu, Huiling Zhang, Yifan Machine Learning Discrete Mathematics 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.
title	HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
topic	Machine Learning Discrete Mathematics
url	https://arxiv.org/abs/2509.15828