论文标题
标准分支的总体复杂性认证和混合二次编程的约束方法
Overall Complexity Certification of a Standard Branch and Bound Method for Mixed-Integer Quadratic Programming
论文作者
论文摘要
本文提出了一种证明标准分支的计算复杂性和界限方法的方法，用于解决混合组合二次编程（MIQP）问题定义为多参数MIQP实例。除了先前的工作之外，不仅考虑了二进制搜索树的大小，还考虑了通过使用Active-Set QP方法的精确复杂性认证的最新结果来解决节点中的松弛的确切复杂性。通过本文提出的算法，为了解决MIQP问题而进行的总数最差的QP迭代数可以确定为问题中参数的函数。该方法的一个重要应用是混合系统的模型预测控制，可以将其作为MIQP配制，必须实时解决。在数值示例中成功说明了所提出的方法的有用性。
This paper presents a method to certify the computational complexity of a standard Branch and Bound method for solving Mixed-Integer Quadratic Programming (MIQP) problems defined as instances of a multi-parametric MIQP. Beyond previous work, not only the size of the binary search tree is considered, but also the exact complexity of solving the relaxations in the nodes by using recent result from exact complexity certification of active-set QP methods. With the algorithm proposed in this paper, a total worst-case number of QP iterations to be performed in order to solve the MIQP problem can be determined as a function of the parameter in the problem. An important application of the proposed method is Model Predictive Control for hybrid systems, that can be formulated as an MIQP that has to be solved in real-time. The usefulness of the proposed method is successfully illustrated in numerical examples.
