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

📄 arXiv: 2509.15828v2 📥 PDF

作者: Ning Xu, Junkai Zhang, Yang Wu, Huigen Ye, Hua Xu, Huiling Xu, Yifan Zhang

分类: cs.LG, cs.DM

发布日期: 2025-09-19 (更新: 2025-09-22)

💡 一句话要点

HyP-ASO：一种混合策略自适应搜索优化框架，用于解决大规模整数线性规划问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 整数线性规划 大邻域搜索 强化学习 自适应优化 混合策略

📋 核心要点

  1. 传统求解器在处理大规模整数线性规划问题时效率低下，主要瓶颈在于其NP-hard的复杂性。
  2. HyP-ASO框架结合定制公式和深度强化学习，自适应地生成高效邻域，从而加速求解过程。
  3. 实验结果表明，HyP-ASO在解决大规模ILP问题上显著优于现有LNS方法，并具有良好的可扩展性。

📝 摘要（中文）

由于大规模整数线性规划（ILP）的NP-hard特性，使用传统求解器直接求解速度缓慢。近年来，基于大邻域搜索（LNS）的框架可以加速求解过程，但其性能往往受到生成足够有效邻域的难度的限制。为了解决这个挑战，我们提出了一种混合策略自适应搜索优化框架HyP-ASO，它结合了定制公式和深度强化学习（RL）。该公式利用可行解来计算邻域生成过程中每个变量的选择概率，而RL策略网络预测邻域大小。大量实验表明，HyP-ASO显著优于现有基于LNS的方法，适用于大规模ILP问题。额外的实验表明，它具有轻量级和高度可扩展性。

🔬 方法详解

问题定义：论文旨在解决大规模整数线性规划（ILP）问题。传统求解器和现有基于大邻域搜索（LNS）的方法在处理此类问题时面临效率瓶颈，尤其是在生成有效邻域方面存在困难。现有LNS方法难以平衡搜索的广度和深度，导致求解效率不高。

核心思路：HyP-ASO的核心思路是结合定制公式和深度强化学习，自适应地生成高质量的邻域。定制公式利用可行解的信息来指导变量的选择概率，而深度强化学习则用于预测合适的邻域大小。这种混合策略旨在克服传统LNS方法在邻域生成方面的局限性，提高搜索效率。

技术框架：HyP-ASO框架主要包含两个核心模块：基于公式的变量选择模块和基于强化学习的邻域大小预测模块。首先，基于公式的模块利用当前可行解的信息，计算每个变量被选入邻域的概率。然后，强化学习策略网络根据当前状态（例如，问题规模、当前解的质量等）预测邻域的大小。最后，根据计算出的概率和预测的邻域大小，生成邻域并进行搜索。

关键创新：HyP-ASO的关键创新在于其混合策略。它将基于公式的启发式方法与深度强化学习相结合，充分利用了可行解的信息和强化学习的自适应能力。这种混合策略能够更有效地生成高质量的邻域，从而加速求解过程。与传统的LNS方法相比，HyP-ASO能够更好地平衡搜索的广度和深度。

关键设计：在基于公式的变量选择模块中，选择概率的计算公式需要根据具体问题进行定制，以充分利用可行解的信息。在基于强化学习的邻域大小预测模块中，策略网络的设计需要考虑到问题的特点和状态空间的维度。损失函数的设计需要能够有效地引导策略网络学习到合适的邻域大小。具体的网络结构和参数设置需要通过实验进行调整和优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，HyP-ASO在解决大规模整数线性规划问题上显著优于现有的基于LNS的方法。具体而言，HyP-ASO在多个测试实例上取得了更优的解，并且求解时间显著缩短。此外，实验还验证了HyP-ASO具有良好的可扩展性，能够有效地处理更大规模的问题。这些结果表明，HyP-ASO是一种高效且实用的求解大规模ILP问题的框架。

🎯 应用场景

HyP-ASO框架可广泛应用于各种需要求解大规模整数线性规划问题的领域，例如供应链优化、资源分配、调度问题、网络设计等。该研究的实际价值在于能够显著提高求解效率，降低计算成本，并为解决复杂的优化问题提供新的思路。未来，该框架可以进一步扩展到其他类型的优化问题，并与其他优化技术相结合，以实现更好的性能。

📄 摘要（原文）

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.