基于Branch ＆Bound方法MIQP问题的求解及应用

研究基于Branch＆Bound(B＆B)方法的混合整数二次规划(Mixed Integer Quadratic Programming，MQP)问题的求解，以及在一类混杂系统优化控制中的应用。B＆B算法求解MIQP问题的过程，可视为对于一个二叉树的搜索。影响B＆B算法寻优效率的两个主要方面是：分支变量的选择规则，以及树搜索策略。通过设定控制变量QPmax，用以限制寻优过程求解QP问题的最大数目，可以在较短的时间内获得MIQP问题的满足整数约束条件次优解。利用MATLAB编制MIQP问题的求解程序，并在混杂系统优化控制中的应用，做了仿真计算。

Branch & Bound Based Solution of MIQP Problem and Its Application

Branch & Bound (B&B) based solution of Mixed Integer Quadratic Programming (MIQP) problem and its application in the optimal control of a class of hybrid systems are studied in this paper. The procedure of finding the optimal solution of MIQP problem can be represented graphically as the exploration of a binary tree. Two main aspects, which affect the efficiency of the B&B algorithm, are branchrules and tree exploration strategies. By introducing QPmax, which specifies the maximum number of QP problems allowed to be solved during exploration, suboptimal solutions of the MIQP problem can be obtained within a short computation time. An MATLAB program is developed as an MIQP problem solver, and simulations are made when applied to the optimal control of a class of hybrid systems.