基于branch_bound方法miqp问题的求解及应用

《基于branch_bound方法miqp问题的求解及应用》由会员分享，可在线阅读，更多相关《基于branch_bound方法miqp问题的求解及应用（4页珍藏版）》请在金锄头文库上搜索。

1、系 统 仿 真 学 报 Vol. 15 No. 4 JOURNAL OF SYSTEM SIMULATION April 2003 488 基于Branch 2浙江大学工业控制技术研究所，杭州 310027) 摘 要：研究基于 Branch MIQP problem; hybrid system; optimal control 引 言1 一类混杂系统的优化控制问题， 最终归结为一个数学规划问题1。由于在该规划问题中同时存在逻辑与连续的决策变量，因而，所归结的为一个混合整数规划问题。事实上，大量的实际问题，如流程工业的生产调度问题2，某些投资项目的决策问题3等，均可以归结为混合整数规划问题。混

2、合整数规划问题，除了很特殊的一些例子，通常是 NP-hard问题。求解混合整数非线性规划问题，比较有效的主要有GBD（Generalized Benders Decomposition）, OA（Outer Approximation） ，Branch 李 平(1954-), 男, 教授, 博导; 王万良(1955-), 男, 教授。 的。 本文研究基于 B & B 方法的 MIQP 问题的详细求解过程，以及在一类混杂系统优化中的应用。首先，把 B & B算法求解 MIQP 问题的过程，视为对一个二叉树的搜索。树的每一节点， 对应于 MIQP 问题的一个松弛 QP 问题。 其次，讨论了影响 B

3、 & B 算法寻优效率的两个主要方面：分支变量的选择规则，以及树搜索策略。本文通过设定控制变量QPmax, 用以限制寻优过程求解 QP 问题的最大数目，可以在较短的时间内获得 MIQP 问题的次优解。最后，利用MATLAB 编制了求解 MIQP 问题的程序，并在一类混杂系统优化控制中的应用，做了仿真计算。 1 B&B算法求解MIQP问题的原理 考虑 MIQP 问题（1）: minFH+ s.t. =nd dnc cdceqeqineqineqRbAbA1 , 0 (1) minFH+s.t. =nd dnc cdceqeqineqineqRRbAbA(2) Vol. 15 No. 4 Apri

4、l 2003 张 聚, 等：基于 Branch & Bound 方法 MIQP 问题的求解及应用 489 问题(1)与连续变量二次规划问题 (Quadratic Programming, QP) (2)的区别在于:问题(1)存在对于部分决策变量取整数值0或 1 的约束条件。 本文限于讨论整数变量的取值为 1或 0的情况， 对于整数变量取一般的整数值情形， 算法的思想是类似的。 B & B 方法求解 MIQP 问题的主要思想是： 通过放松决策变量中d的部分或全部的整数约束限制， 生成一系列对应原来 MIQP 问题的 QP 问题；通过求解这一系列的 QP 问题可以得到符合整数约束条件的 MIQP

5、问题的解 （次优解或全局最优解） 。而求解 QP 问题，是比较容易的，可以直接借助 MATLAB Optimization Toolbox 中现有的求解QP 问题的程序来完成。 B & B方法求解MIQP问题的原理可借助完全二叉树的数据结构来表示。令nd, 1 , 0是一向量，它的维数与决策变量中限制为整数约束的d的维数相同。对应二叉树中的一个节点，也对应一个 QP 问题。中元素的取值（范围）相应于d中对应变量在 QP 问题中的取值（范围） 。当中的某一元素的值取为*时，表示该元素可以取0,1之间任意的实数值。 对 MIQP 问题，放松决策变量中所有取整数值的约束 条件后，用0表示。则444

6、3444 21 nd*.*0=，0对应于二叉 树的树根。0所表示的即 QP 问题（2） 。借助于 MATLAB提供的求解 QP 问题的现有的程序，即可得到QP 问题（2）的最优决策变量R以及目标函数的最优值Rf。若问题（2）无解或=Rf，则原来的 MIQP 问题也无解。若R满足整数约束条件（即R中的d全为整数值 0 或 1） ，则R即为原MIQP 问题的全局最优解。若R不满足整数约束条件， 则必须在0的基础上，进一步生成QP 问题，并求解这些问题。在0的基础上，进一步生成 QP 问题的方法是：选择0中的某一元素（事实上，元素的选择方法对于算法的寻优效率有影响） ，分别设定该元素的值为 0和 1

7、。 在二叉树上， 对应节点0（选择第二个元素）生成的两个子节点,12如图 1 所示。 44 344 2144 344 21 ndnd*.*1*.*0*2 , 1=对应1的 QP 问题(3)为： minFH+ s.t.= =,.)4, 3(#)(#0)2()1(2nd dddnc cdceqeqineqineqRRRbAbA (3) 对应2的 QP 问题(4)为 minFH+ s.t. = =,.)4 ,3(#)(#1)2()1(2nd dddnc cdceqeqineqineqRRRbAbA (4) 问题(3)(4)通过适当的变化，可以转化为标准的 QP 问题求解。 图 2 为具有 3 个整数

8、变量约束的 MIQP 问题对应的完全二叉树。 每一个节点对应一个向量， 也对应一个 QP 问题。 2 B&B算法求解MIQP问题的步骤 B&B算法求解MIQP问题的步骤概括如下 1 对应向量0的 QP 问题，初始化 QP 问题集合；初始化设置=+=. ,optoptf。 设定控制变量QPmax, 用以限制寻优过程求解 QP 问题的最大数目。 2 如果 QP 问题集合为空集，或求解的 QP 问题的数目已达到 QPmax，则停止计算，求得问题的全局最优解optf,opt或次优解suboptf,subopt。若求解结束得到的+=optf或+=suboptf， 则原先的 MIQP 问题是不可解的。 3

9、 从 QP 问题的集合中选择一个做为当前待求解的QP 问题，并从 QP 问题的集合中删除该 QP 问题。 4 求解当前的 QP 问题。记它的解为Rf，R。 5 由 4 求解 QP 问题可能得到以下的几种情况： 1) 若当前的 QP 问题是无解的。显然，以该 QP 问题为根节点的子树内所有其它节点对应的 QP 问题也是无解的，因而就无需计算他们对应的 QP 问题。跳至 2。 2) 若optRff 。显然，以该 QP 问题为根节点的子树内所有其它节点对应的 QP 问题的解也是大于optf的，因而就无需计算他们对应的 QP 问题。跳至 2。 3) 若optRff ，且满足整数约束条件，则当前 QP问

10、题的解即为到目前为止求得的 MIQP 问题的最优的解。RoptRffopt= ,。跳至 2。 4) 若optRff ，但是不满足整数约束条件，跳至 6。 图 1 由父节点生成两个子节点 图 2 具有 3 个整数变量约束的 MIQP 问题对应的完全二叉树 Vol. 15 No. 4 系 统 仿 真 学 报 April 2003 490 6 在当前的 QP 问题的基础上，生成两个新的 QP 问题，并加入到 QP 问题的集合中。跳至步骤 2。 从以上的求解步骤，可以看到，B & B算法求解 MIQP问题，在最差的情况下，所需要的求解 QP 问题的数目为：121+nd。因而，本质上是隐枚举，非多项式的

11、算法。但从步骤 5 1） ，2）可以看到，当某一子树的根节点对应的 QP问题无解或optRff 时，则该子树内其他节点对应的QP 问题也就无需求解。从而，大大减少需要求解的 QP 问题的数量。若这样子树的规模越大，越多，则算法就越有效。这也是 B & B 算法，在通常的情况下，求解 MIQP 问题较有效的主要原因。 从上述的求解步骤可以看到， 在 B & B 方法求解 MIQP问题的过程中， 不断地求得 MIQP 问题的符合整数约束条件的越来越接近最优的次优解，如果计算时间允许，将最终得到 MIQP 问题的全局最优解。 如果由于计算时间的限制 （比如在线优化计算的需要） ，不允许我们有足够的时

12、间求得全局最优解，我们可以通过设定算法在寻优过程中允许求解QP 问题的最大数目， 以在较短的时间内获得问题的次优解。 从上述的求解步骤中还可以看到：影响 B & B算法计算效率的两个主要因素是：B& B 算法的分支规律（对应步骤 6）与树搜索策略（对应步骤 3） 。 在求解 MIQP 问题的程序中， B & B 算法考虑了以下的变量分支规律，以供选用： (1)、First Free Variable 规律, 即选择中，下标最小的松驰变量为分支变量。图 2 就是采用这种分支规律。 (2)、Fractional Part Based 规律，即选择中，离相邻整数 0 或 1 距离最近或最远的松驰变量

13、为分支变量。 在求解 MIQP 问题的程序中，B& B 算法考虑了以下的树搜索策略，以供选用： (1)、深度优先树搜索策略。按这种搜索策略，B&B 算法最后生成的 QP 问题，将最先被选择来计算，图 3a。这种搜索策略易于用堆栈数据结构来实现。 (2)、宽度优先树搜索策略。图 3b。同一深度内的选择次序是任意的。 (3)、值优先策略。选择那些父QP 问题具有较小目标函数值的 QP 问题优先计算。 针对以上 B & B 算法求解 MIQP 问题的步骤，考虑以上几种分支规律和树搜索策略，应用 MATLAB 编制程序，以实现上述的计算步骤。 图 3a 按深度优先搜索策略 图 3b 按宽度优先搜索策略

14、 节点对应的 QP 问题的计算次序 节点对应的 QP 问题的计算次序 3 应用及仿真算例 MLD 模型描述的一类混杂系统的二次性能指标优化控制问题，最终归结为对于 MIQP 问题的求解，详见文献1。利用上面讨论的基于 B&B 算法的 MIQP 问题求解步骤，对混杂系统1的优化控制问题做了数值仿真计算。 仿真计算1， 系统的初态 ,2 , 20=x末态, ,xf00=控制输入 1 , 1)(tu，控制时域长度 T=7. 求解 MIQP 问题（含 7 个整数变量约束，dn=7） ，最优控制结果如图(4a-4c)所示（QPmax 无限制） 。图 4c 为 MIQP 问题所含整数约束的变量在最优解时的值。 图 4a 系统的最优状态轨迹 图 4b 最优控制输入 图 4c 辅助逻辑变量 图 4 仿真计算 1 结果 仿真计算2, 比较不同的 QPmax 取值，对于控制结果的影响（分别求得最优解与次优解） 。系统的初态,2 , 20=x末态, ,xf11 = 3 , 3)(tu，T=10。控制的结果如图 5。 仿真计算3, 比较不同的树搜索策略，对于控制结果的影响。系统的参数同仿真计算 2。控制结果如图 6。 仿真计算4, 比较不同的分支变量规律，对于控制结果的影响。系统的参数同仿真计算 2。控制结果如图 7。 Trajectory of Auxiliary Logical Variab