提出分层条件解法预测框架,显著降低混合整数规划求解差距。
SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

- 构建变量耦合图,分层递进预测变量值,逐层依赖先前结果。
- 在4个标准基准上实现平均54%的解差距下降,优于单次预测方法。
- 适合需要高效求解大规模优化问题的研究者与工程应用。
混合整数线性规划(MILP)是组合优化中的基础范式,广泛应用于真实场景。由于其NP-hard特性,对大规模或高度约束的MILP实例求得最优解仍计算代价高昂。基于学习的解预测因此成为加速求解器的有前景方法。然而,现有方法多采用一次性预测范式,同时预测所有变量的边际概率,仅通过消息传递隐式捕捉变量间的条件依赖,组合结构建模完全依赖图神经网络的表示能力。为解决此局限,本文提出结构感知分层解法预测(SHSP)框架,以新型分层条件解码机制替代原有并行边际解码。具体而言,SHSP从约束结构构建变量耦合图,沿耦合强度递增的层次序列化解码变量,并在每层条件化于先前预测结果。为缓解解码过程中的误差累积,还引入置信度感知的掩码与修复机制,识别并修正不可靠的中间预测。将SHSP集成至多种学习引导搜索方法,在四个标准MILP基准上评估,实验表明其显著优于现有一次性预测基线,平均解差距降低54%。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignment for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods, and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。