A Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming

📄 arXiv: 2503.16235v2 📥 PDF

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

分类: eess.SY

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

💡 一句话要点

提出统一的复杂度认证框架，保障混合整数规划分支定界算法的实时性

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

关键词: 混合整数规划 模型预测控制 分支定界算法 复杂度认证 实时优化

📋 核心要点

  1. 混合MPC对实时性要求高，高效求解带计算复杂度保证的MILP/MIQP问题是关键，现有方法缺乏对分支定界算法复杂度的系统性认证。
  2. 提出统一的复杂度认证框架，可为基于分支定界算法的MILP/MIQP求解器提供最坏情况计算复杂度的保证，并考虑了多种策略和启发式方法。
  3. 数值实验验证了该框架在随机MILP/MIQP以及混合MPC问题中的有效性，为求解器定制提供了理论保证和实践指导。

📝 摘要（中文）

本文针对混合系统模型预测控制(MPC)中，求解混合整数线性规划(MILP)和混合整数二次规划(MIQP)问题对实时性的需求，提出了一种统一的复杂度认证框架，用于基于分支定界(B&B)的MILP和MIQP求解器。该框架针对多参数MILP和MIQP问题，提供了最坏情况计算复杂度的保证，包括B&B算法达到最优解所需的最大迭代次数或松弛次数。该框架系统地考虑了不同的分支和节点选择策略，以及集成到B&B中的启发式方法，确保了全面的认证。通过为求解器定制提供理论保证和实践见解，该框架增强了B&B在实时应用中的可靠性。数值实验表明，该框架在随机MILP和MIQP以及混合MPC问题中的MIQP上均有效。

🔬 方法详解

问题定义：在混合系统模型预测控制(MPC)中，需要高效且有计算复杂度保证地求解混合整数线性规划(MILP)和混合整数二次规划(MIQP)问题。现有的分支定界(B&B)算法虽然常用，但缺乏对最坏情况计算复杂度的系统性认证，难以满足实时性要求。现有方法无法保证在限定时间内找到最优解，或者无法提供算法复杂度的上界。

核心思路：本文的核心思路是构建一个统一的复杂度认证框架，该框架能够对基于B&B的MILP和MIQP求解器进行认证，提供最坏情况下的计算复杂度保证。通过分析B&B算法的各个组成部分（如分支策略、节点选择策略、启发式方法等）对算法复杂度的影响，从而建立一个能够系统性地评估算法复杂度的框架。这样设计的目的是为了确保在实时应用中，B&B算法能够在限定时间内找到最优解，或者至少能够提供算法复杂度的上界。

技术框架：该框架主要包含以下几个模块：1) 问题建模：将MILP/MIQP问题转化为框架可处理的形式。2) 算法分析：分析B&B算法中各个组成部分对复杂度的影响。3) 复杂度认证：基于算法分析的结果，计算最坏情况下的计算复杂度上界。4) 求解器定制：根据复杂度认证的结果，对求解器进行定制，以满足实时性要求。整个流程从问题建模开始，经过算法分析和复杂度认证，最终实现求解器的定制。

关键创新：该框架的关键创新在于其统一性和系统性。它不仅能够处理MILP和MIQP问题，还能够系统性地考虑不同的分支和节点选择策略，以及集成到B&B中的启发式方法。与现有方法相比，该框架能够提供更全面的复杂度认证，从而更好地满足实时应用的需求。此外，该框架还为求解器定制提供了理论保证和实践指导，使得用户可以根据实际需求对求解器进行优化。

关键设计：该框架的关键设计在于对B&B算法中各个组成部分的建模和分析。例如，对于分支策略，需要考虑不同的分支变量选择方法对算法复杂度的影响；对于节点选择策略，需要考虑不同的节点选择规则对算法复杂度的影响；对于启发式方法，需要考虑启发式方法对搜索空间的影响。此外，还需要设计合适的数学模型，将这些影响因素纳入到复杂度认证的计算中。

🖼️ 关键图片

img_0

📊 实验亮点

数值实验表明，该框架在随机生成的MILP和MIQP问题以及来自混合MPC问题的MIQP上均表现良好。实验结果验证了该框架能够有效地对B&B算法的复杂度进行认证，并为求解器定制提供有价值的指导。具体性能数据（如迭代次数、求解时间等）在论文中进行了详细展示，并与未进行复杂度认证的B&B算法进行了对比，显示出显著的性能提升。

🎯 应用场景

该研究成果可广泛应用于混合系统的模型预测控制(MPC)领域，尤其是在对实时性要求较高的场景下，例如自动驾驶、机器人控制、电力系统调度等。通过该框架，可以为MILP/MIQP求解器提供计算复杂度保证，从而确保控制系统的稳定性和可靠性。此外，该框架还可以用于求解器定制，提高求解效率，降低计算成本。

📄 摘要（原文）

In model predictive control (MPC) for hybrid systems, solving optimization problems efficiently and with guarantees on worst-case computational complexity is critical to satisfy the real-time constraints in these applications. These optimization problems often take the form of mixed-integer linear programs (MILPs) or mixed-integer quadratic programs (MIQPs) that depend on system parameters. A common approach for solving such problems is the branch-and-bound (B&B) method. This paper extends existing complexity certification methods by presenting a unified complexity-certification framework for B&B-based MILP and MIQP solvers, specifically for the family of multi-parametric MILP and MIQP problems that arise in, e.g., hybrid MPC applications. The framework provides guarantees on worst-case computational measures, including the maximum number of iterations or relaxations B&B algorithms require to reach optimality. It systematically accounts for different branching and node selection strategies, as well as heuristics integrated into B&B, ensuring a comprehensive certification framework. By offering theoretical guarantees and practical insights for solver customization, the proposed framework enhances the reliability of B&B for real-time application. The usefulness of the proposed framework is demonstrated through numerical experiments on both random MILPs and MIQPs, as well as on MIQPs arising from a hybrid MPC problem.