arXiv:2604.09556cs.DCcs.AI2026-04

提出首个开源确定性并行分支定界法,解决MIP求解中的负载不均问题。

Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP

  • 通过复制完整求解状态实现确定性并行,避免非确定性同步
  • 基于结构特征与历史数据的多阶段预测模型提升负载均衡效率
  • 在80个测试实例上实现8线程下2.17倍加速,高复杂度任务达5.12倍

混合整数规划(MIP)通过引入连续与整数决策变量扩展了线性规划,广泛应用于生产计划、物流调度和资源分配。然而,MIP属于NP难问题,通常无法在多项式时间内求得最优解。分支定界作为基础精确算法,在商业应用中因计算异构性和严格确定性要求面临显著并行化挑战。本文首次实现了HiGHS这一高性能MIP求解器的全开源确定性并行分支定界框架。方法采用新型数据并行架构,通过在工作线程间复制完整求解状态确保严格确定性,消除非确定性同步原语。核心创新在于基于人工智能的负载均衡机制:利用多阶段工作负载预测模型,根据节点结构特征与历史性能数据估算计算复杂度,并结合动态参数调整策略。框架执行包括并发深搜、系统化数据合并与智能节点选择在内的协同并行阶段。在80个MIPLIB 2017基准实例上的综合实验表明,使用8线程时几何平均加速比达2.17,同时保持完全确定性;对于计算密集型实例,加速比最高达5.12,线程空闲率平均为34.7%。

原文摘要 · Abstract (English)

Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables, making it widely used in production planning, logistics scheduling, and resource allocation. However, MIP remains NP-hard and cannot generally be solved to optimality in polynomial time. Branch-and-bound, a fundamental exact method, faces significant parallelization challenges due to computational heterogeneity and strict determinism requirements in commercial applications. This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver. Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads and eliminating non-deterministic synchronization primitives. A key innovation is our AI-driven load balancing mechanism employing multi-stage workload prediction models that estimate node computational complexity based on structural characteristics and historical performance data, coupled with dynamic parameter adjustment strategies. The framework executes orchestrated parallel phases including concurrent dive operations, systematic data consolidation, and intelligent node selection. Comprehensive experimental evaluation on 80 MIPLIB 2017 benchmark instances demonstrates effectiveness, achieving a geometric mean speedup of 2.17 using eight threads while maintaining complete deterministic guarantees. Performance gains become increasingly pronounced for higher node counts, with speedup factors reaching 5.12 for computationally intensive instances and thread idle rates averaging 34.7%.

MIP求解并行计算负载均衡确定性

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