Parallel Domain-Decomposition Algorithms for Complexity Certification of Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming

📄 arXiv: 2503.16411v2 📥 PDF

作者: Shamisa Shoja, Daniel Arnström, Daniel Axehill

分类: eess.SY

发布日期: 2025-03-20 (更新: 2025-04-10)

💡 一句话要点

提出并行域分解算法，加速混合整数规划分支定界算法的复杂度认证。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 混合整数规划 模型预测控制 复杂度认证 并行计算 域分解

📋 核心要点

  1. 混合整数规划求解器复杂度认证对于混合系统实时模型预测控制至关重要，但现有方法难以扩展到大规模问题。
  2. 论文提出并行域分解算法，将问题分解为多个子问题并行求解，并优化内存管理，从而加速复杂度认证过程。
  3. 实验结果表明，该并行算法在保证正确性的前提下，显著降低了计算时间，验证了其在大规模问题上的有效性。

📝 摘要（中文）

本文针对线性或二次性能指标的混合系统模型预测控制(MPC)中，需要求解混合整数线性规划(MILP)或混合整数二次规划(MIQP)的问题，提出了一种并行域分解算法，用于加速分支定界(B&B)算法的计算复杂度认证。该算法扩展了先前的工作，使其能够处理更大规模的问题，并利用高性能计算(HPC)资源。此外，为了降低峰值内存消耗，本文对现有的(串行)复杂度认证框架进行了两项改进，并将它们集成到所提出的并行算法中。数值实验表明，该并行算法在保持原始框架正确性的同时，显著减少了计算时间。

🔬 方法详解

问题定义：论文旨在解决多参数混合整数线性规划(mp-MILP)和多参数混合整数二次规划(mp-MIQP)的分支定界(B&B)算法的计算复杂度认证问题。现有串行算法在处理大规模问题时面临计算时间长和内存消耗大的挑战，限制了其在实时混合MPC应用中的应用。

核心思路：论文的核心思路是将原始问题分解为多个较小的子问题，并利用并行计算资源同时求解这些子问题。通过域分解技术，将原始问题的可行域划分为多个子域，每个子域对应一个独立的子问题。这种方法可以显著减少每个子问题的规模，从而降低计算复杂度。

技术框架：该算法主要包含以下几个阶段：1) 问题分解：将原始mp-MILP/mp-MIQP问题分解为多个子问题，每个子问题对应一个子域。2) 子问题求解：利用并行计算资源，同时求解各个子问题，得到每个子域的复杂度认证结果。3) 结果合并：将各个子问题的复杂度认证结果合并，得到原始问题的整体复杂度认证结果。此外，为了降低内存消耗，论文还引入了两种内存优化技术。

关键创新：论文的关键创新在于提出了并行域分解算法，并将其应用于mp-MILP/mp-MIQP问题的复杂度认证。与现有串行算法相比，该算法能够充分利用并行计算资源，显著减少计算时间。此外，论文还提出了两种内存优化技术，进一步降低了算法的内存消耗。

关键设计：论文中域分解的具体实现方式未知，但可以推测其目标是平衡各个子问题的计算量，并尽量减少子问题之间的依赖关系。内存优化技术的具体细节也未知，但可能包括数据压缩、内存共享等策略。并行计算框架的选择和配置也是关键设计之一，需要根据具体的计算资源和问题规模进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

数值实验表明，所提出的并行域分解算法能够显著减少计算时间，具体性能提升幅度取决于问题的规模和并行计算资源的数量。虽然论文没有给出具体的性能数据，但强调了该算法在保持原始框架正确性的前提下，实现了计算效率的提升。此外，论文还提到，所提出的内存优化技术能够有效降低峰值内存消耗。

🎯 应用场景

该研究成果可应用于混合系统的实时模型预测控制(MPC)领域，尤其适用于对计算资源有限制或对实时性要求高的场景。通过对MILP/MIQP求解器的复杂度进行认证，可以保证MPC算法在最坏情况下的计算时间，从而提高系统的可靠性和安全性。此外，该方法还可以应用于其他需要求解大规模MILP/MIQP问题的领域，如优化调度、资源分配等。

📄 摘要（原文）

When implementing model predictive control (MPC) for hybrid systems with a linear or a quadratic performance measure, a mixed-integer linear program (MILP) or a mixed-integer quadratic program (MIQP) needs to be solved, respectively, at each sampling instant. Recent work has introduced the possibility to certify the computational complexity of branch-and-bound (B&B) algorithms when solving MILP and MIQP problems formulated as multi-parametric MILPs (mp-MILPs) and mp-MIQPs. Such a framework allows for computing the worst-case computational complexity of standard B&B-based MILP and MIQP solvers, quantified by metrics such as the total number of LP/QP iterations and B&B nodes. These results are highly relevant for real-time hybrid MPC applications. In this paper, we extend this framework by developing parallel, domain-decomposition versions of the previously proposed algorithm, allowing it to scale to larger problem sizes and enable the use of high-performance computing (HPC) resources. Furthermore, to reduce peak memory consumption, we introduce two novel modifications to the existing (serial) complexity certification framework, integrating them into the proposed parallel algorithms. Numerical experiments show that the parallel algorithms significantly reduce computation time while maintaining the correctness of the original framework.