arXiv:2601.16056cs.AI2026-01

用深度学习自动学习最优求解路径,提升整数规划求解速度。

Designing faster mixed integer linear programming algorithm via learning the optimal path

  • 基于深度学习构建节点选择机制,自动捕捉求解路径中的关键特征。
  • 在三个NP难基准上显著减少求解时间,最快提速超3倍。
  • 能泛化到复杂大规模实例,可替代人工设计的启发式规则。

设计更高效的混合整数线性规划(MILP)求解算法在众多实际领域中至关重要,因为大量复杂现实问题可建模为MILP。求解通常采用分支定界法,其核心是搜索包含最优解的节点路径。传统方法依赖人工设计的启发式策略,性能不稳定且难以跨实例泛化。为此,本文提出DeepBound,一种基于深度学习的节点选择算法,通过数据自动学习人类直觉。其核心在于多层级特征融合网络,以捕获节点表示;针对分支定界树中节点分布不均问题,采用成对训练范式增强判别能力。在三个NP难MILP基准上的实验表明,DeepBound在求解效率上优于传统启发式与现有学习方法,显著缩短计算时间并获得最优可行解。同时,其在大型复杂实例上表现出强泛化能力。对学习特征的分析显示,该方法可自动发现更灵活、鲁棒的特征选择机制,有望改进甚至取代人工设计的启发式规则。

原文摘要 · Abstract (English)

Designing faster algorithms for solving Mixed-Integer Linear Programming (MILP) problems is highly desired across numerous practical domains, as a vast array of complex real-world challenges can be effectively modeled as MILP formulations. Solving these problems typically employs the branch-and-bound algorithm, the core of which can be conceived as searching for a path of nodes (or sub-problems) that contains the optimal solution to the original MILP problem. Traditional approaches to finding this path rely heavily on hand-crafted, intuition-based heuristic strategies, which often suffer from unstable and unpredictable performance across different MILP problem instances. To address this limitation, we introduce DeepBound, a deep learning-based node selection algorithm that automates the learning of such human intuition from data. The core of DeepBound lies in learning to prioritize nodes containing the optimal solution, thereby improving solving efficiency. DeepBound introduces a multi-level feature fusion network to capture the node representations. To tackle the inherent node imbalance in branch-and-bound trees, DeepBound employs a pairwise training paradigm that enhances the model's ability to discriminate between nodes. Extensive experiments on three NP-hard MILP benchmarks demonstrate that DeepBound achieves superior solving efficiency over conventional heuristic rules and existing learning-based approaches, obtaining optimal feasible solutions with significantly reduced computation time. Moreover, DeepBound demonstrates strong generalization capability on large and complex instances. The analysis of its learned features reveals that the method can automatically discover more flexible and robust feature selection, which may effectively improve and potentially replace human-designed heuristic rules.

整数规划深度学习分支定界算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。