整数二次规划问题的一种新型分支定界算法

刘 霞，高岳林

（北方民族大学 信息与系统科学研究所，宁夏 银川750021）

整数规划问题是带整数变量的最优化问题，即在受约束于一组等式或不等式约束条件下最大化或最小化一个全部或部分变量为整数的多元函数的最优化问题［1］.整数规划的应用较为广泛，许多工程技术、社会科学、金融以及工商管理等决策问题都可用其描述.随着科学技术的发展以及现实中许多决策问题研究的迫切需要，非线性整数规划问题的算法研究已经成为运筹学及最优化领域的研究热点之一［2］.通常研究的整数规划问题是线性的，而一般的线性整数规划问题是NP难的，非线性整数规划问题的难度更大.求解非线性整数规划问题的确定性方法有外逼近法［3-4］、割平面法［5-7］、分解算法［8-9］和分支定界法［10-15］等.已知整数规划问题是NP难问题，而现有的算法只能用于求解整数规划问题的某些特殊形式，并且常常具有收敛速度慢、计算量大、效率差等许多不足.为了寻求一个可以广泛而有效地求解一般非线性整数规划问题的算法，本文考虑以下特殊的非线性整数规划问题——整数二次规划问题

其中，Q∈Rn×n是对称矩阵是非空有界集.

1 松弛定界方法

首先构造包含原问题（IQP）可行域的整超矩形R.当j∈｛1，2，…，n｝时，计算以下2n个线性规划问题

由式（1）得最优解h＊j，由式（2）得最优解l＊j.令

可得到包含可行域F=D∩Zn的整超矩形

其中，x-=（x-1，x-2，…，x-n）T，¯x=（¯x1，¯x2，…，¯xn）T是整数向量.于是原（IQP）问题等价为以下问题（IPQ）′：

下面考虑问题（IQP）′的连续松弛规划问题（QP）：

首先考虑问题（QP）最优值下界的估计.设λmin是矩阵Q的最小特征值，若λmin≥0，则令θ=0，否则令θ=|λmin|+τ，其中τ≥0，令τ=10-7，因此Q+θI半正定.在矩形Rk=｛x∈Rn|x-k≤x≤¯xk｝⊂R上，构造f（x）在Rk上的一个线性下界函数.由于

因此

其中

定理1 设ρ（Q+θI）是半正定矩阵Q+θI的谱半径，则

证明 由式（3）～（5）得

因此，结论成立.证毕.

于是得到问题（QP）在矩形Rk上的线性松弛规划问题

求解问题（LP（Rk））得到其最优值，它的最优值是问题（QP）在Rk上的全局最优值ν（QP）的一个下界，也是原问题（IQP）在Rk上的全局最优值的一个有效下界.即

定上界：通过剖分和缩减超矩形过程中不断地产生原问题（IQP）的可行点来更新上界.

2 超矩形的剖分与缩减

2.1 超矩形的剖分

Step 2 通过x′与xk的连线或连线所在的平面把超矩形Rk剖分为两个子超矩形其中边取整剖分为两部分，则子超矩形Rk1=中的左下顶点和右上顶点分别为

2.2 超矩形的缩减

为方便叙述，把新产生的超矩形仍记为Rk，是原来超矩形的子集.问题（IQP）中的所有线性不等式约束可变形为然后使用文献［14］中的超矩形缩减算法进行缩减.

3 新型分枝定界算法

到第k步迭代时，要剖分的超矩形和问题（IQP）的可行域分别用Rk和F表示，当前找到的所有可行点的集合和剪枝后剩下的超矩形的集合分别用W和T表示.问题（LP（Rk））在超矩形Rk上的最优解和最优值分别用xk和ν（Rk）表示，当前全局最优解和最优值分别用xν∈arg minν和ν=min｛ν（Rk）：Rk∈T｝表示.问题（IQP）的全局最优值的一个下界和上界分别用ν和γ表示，ν对应的超矩形用Rν表示.

算法描述：

Step 2（终止条件） 若ν=γ，则终止.输出问题（IQP）的全局最优解xγ和全局最优值f（xγ）；否则转到step3.

Step 3（选择规则） 在T中选择ν对应的超矩形Rk，即ν=ν（Rk）；

Step 4（剖分方法） 若xk∈Zn，则删除保留最优解xk；否则运用2.1中的给出的超矩形剖分方法对超矩形Rk进行剖分，剖分后的两个子超矩形为Rk1，Rk2，并且满足

Step 5（缩减技术） 运用2.2中给出的超矩形缩减技术缩减剖分后的子超矩形，新的超矩形仍记为Rki，i∈Γ，其中Γ表示缩减后的超矩形的指标集；

Step 6（定上界）

Step 8（定下界）

置k←k+1.转到Step 2.

4 数值实验

下面采用MATLAB 7.8.0编程，通过大量的数值实验对提出的新算法和文献［14］中的算法进行测试，说明该新算法的可行性、有效性以及优越性.所有测试均在Intel（R）Core（TM）i5-3570 K，CPU＠3.40 GHz，4.00 GB内存，32位操作系统计算机上运行.

为了使所测试的算例更具有说服力，并便于与文献［14］进行对比，仿照文献［14］的算例，针对不同阶数和条件数，在MATLAB中随机生成不同性态的矩阵Q以及目标函数的一次项向量c，约束条件从表5中选取.针对提出的新算法，表1～3分别给出矩阵Q正定、负定、不定时规模不同、约束不同和矩阵Q性态不同的整数二次规划问题的测试结果，表4给出了矩阵Q的规模和约束相同但性态不同时的几个100维问题的测试结果.所有表中的“约束序号”均表示该算例的约束条件在表5中所对应的序号，“Q性态”表示矩阵Q的2-范数条件数，“时间”列中的“算法1”表示文章提出的新算法，“算法2”表示文献［14］中的算法，“整数最优值”表示算法终止时目标函数的最优值，“近似最优值”表示松弛问题的最优值.

表1 Q正定时的整数二次规划问题的计算结果 Tab.1 Calculation results of integer quadratic programming problems when Q is positive definite

表2 Q负定时的整数二次规划问题的计算结果 Tab.2 Calculation results of integer quadratic programming problems when Q is negative definite

表3 Q不定时的整数二次规划问题的计算结果 Tab.3 Calculation results of integer quadratic programming problems when Q is indefinite

表4 性态不同的整数二次规划问题的计算结果 Tab.4 Calculation results of integer quadratic programming problems with different condition

表5［14］ 不同测试算例中使用的约束条件 Tab.5 Constraints be used in different test examples

从表中可以看出，随着问题规模、有效约束以及矩阵Q条件数的增加，问题的求解时间也在增加，复杂度自然就增加.将提出的新算法和文献［14］中的算法进行比较，发现针对同等规模的问题，所提出的新型分支定界算法的计算时间远小于文献［7］所提出算法的计算时间，该算法提高了计算效率.

5 结 论

本文研究表明，该新型分支定界算法大大缩短了计算时间，提高了计算效率，对于中大规模的整数二次规划问题效果更为明显.该算法可用来求解不同规模、不同条件数的整数二次规划问题，具有广泛适用性，算法有效快捷.另外，在分支定界方法中，分支变量和分支方向的选取会影响分支定界算法的效率，这将是下一步研究的问题.

［1］孙小玲，李端.整数规划新进展［J］.运筹学学报，2014，18（1）：39-68.Sun Xiaoling，Li Duan.Recent advances in integer programming［J］.Operations Research Transactions，2014，18（1）：39-68.（in Chinese）

［2］黄红选，梁治安.全局优化引论［M］.北京：清华大学出版社，2003.

［3］Buchheim C，Trieu L.Quadratic outer approximation for convex integer programming with box constraints［J］.Lecture Notes in Computer Science，2013，7933：224-235.

［4］Fletcher R，Leyffer S.Solving mixed intger nonlinear programs by outer approximation［J］.Mathematical Programming，1994，66（1-3）：327-349.

［5］Westerlund T，Pettersson F.An extended cutting plane method for solving convex MINLP problems［J］.Computer and Chemical Engineering，1995，19：131-136.

［6］Nowak I，Vigerske S.LaGO：a（heuristic）branch and cut algorithm for nonconvex MINLPs［J］.Central European Journal of Operations Research，2008，16（2）：127-138.

［7］Eronena V P，Mäkeläa M M，Westerlundb T.Extended cutting plane method for a class of nonsmooth nonconvex MINLP problems［J］.Optimization，2013：796473.

［8］Flippo O E，Rinnoy Kan A H G.A note on benders decomposion in mixed-integer quadratic programming［J］.Operations Research Letters，1990，9（2）：81-83.

［9］Sun X L，Li J L，Luo H Z.Convex relaxation and Lagrangian decomposition for indefinite quadratic integer programming［J］.Optimization，2010，59（5）：627-641.

［10］Thoai N V.Global optimization techniques for solving the general quadratic integer programming problem［J］.Computational Optimization and Applications，1998，10（2）：149-163.

［11］陈志平，郤峰.求解中大规模复杂凸二次整数规划问题的新型分枝定界算法［J］.计算数学，2004，26（4）：445-458.Chen Zhiping，Xi Feng.A new branch-and-bound algorithm for solving large complex integer convex quadratic programs［J］.Mathematic Numerica Sinica，2004，26（4）：445-458.（in Chinese）

［12］Gao Y L，Wang Y J，Du X W.A two-level relaxed bound method for a nonlinear class of 0-1 knapsack problems［J］.Intelligent Information，Management Systems and Technologies，2005，3：461-470.

［13］Zhu W X.A provable better branch and bound method for a nonconvex integer quadratic programming problem［J］.Journal of Computer and System Sciences，2005（70）：107-117.

［14］高岳林，魏飞.一类非负二次整数规划问题的分支定界缩减方法［J］.计算数学，2011，33（3）：233-248.Gao Yuelin，Wei Fei.A branch-and-bound reduced method for a class of non-negative integer quadratic programming problems［J］.Mathematic Numerica Sinica，2011，33（3）：233-248.（in Chinese）

［15］Misener R，Floudas C A.Glo MIQO：global mixedinteger quadratic optimizer［J］.Journal of Global Optimization，2013，57（1）：3-50.