arXiv:2511.21107cs.LGcs.AI2025-11

通过动态分层对比学习,提升分支定界法中节点的判断精度与求解效率。

Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching

  • 按节点特征分布分层,用图卷积模型逐步区分不同组别节点。
  • 上游节点数据稀疏问题缓解,生成等价与扰动实例增强训练数据。
  • 显著提升上游节点分支准确率,对未见实例有良好泛化能力。

混合整数线性规划(MILP)是典型的NP难问题,在学术界和工业界均受广泛关注。分支定界法(B&B)是求解MILP的主要方法,其中分支策略起关键作用。近年来,基于神经网络的学习框架被用于优化分支策略,以提高求解效率。然而,现有方法仍面临深度间语义差异、上游节点样本稀缺以及强分支样本采集成本高等挑战。为此,本文提出一种动态分层对比学习框架( ours),根据分支定界树中节点的特征分布进行分组,并训练基于图卷积网络(GCNN)的判别模型,实现跨组节点的渐进式分离,从而学习更细粒度的节点表示。为缓解上游节点的数据稀缺与不平衡问题,引入一种上游增强的MILP衍生方法,生成理论等价及扰动实例。实验结果表明, ours 能有效捕捉节点间的细微语义差异,在标准MILP基准测试上显著提升分支准确率与求解效率,尤其在上游节点表现优异,并具备对未见实例的良好泛化能力。

原文摘要 · Abstract (English)

Mixed Integer Linear Programming (MILP) is a fundamental class of NP-hard problems that has garnered significant attention from both academia and industry. The Branch-and-Bound (B\&B) method is the dominant approach for solving MILPs and the branching plays an important role in B\&B methods. Neural-based learning frameworks have recently been developed to enhance branching policies and the efficiency of solving MILPs. However, these methods still struggle with semantic variation across depths, the scarcity of upstream nodes, and the costly collection of strong branching samples. To address these issues, we propose \ours, a Dynamic \underline{\textbf{S}}tratified \underline{\textbf{C}}ontrastive Training Framework for \underline{\textbf{MILP}} Branching. It groups branch-and-bound nodes based on their feature distributions and trains a GCNN-based discriminative model to progressively separate nodes across groups, learning finer-grained node representations throughout the tree. To address data scarcity and imbalance at upstream nodes, we introduce an upstream-augmented MILP derivation procedure that generates both theoretically equivalent and perturbed instances. \ours~effectively models subtle semantic differences between nodes, significantly enhancing branching accuracy and solving efficiency, particularly for upstream nodes. Extensive experiments on standard MILP benchmarks demonstrate that our method enhances branching accuracy, reduces solving time, and generalizes effectively to unseen instances.

MILP分支策略图神经网络对比学习

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