求解中大规模复杂凸二次整数规划问题的新型分枝定界算法

针对现有分枝定界算法在求解高维复杂二次整数规划问题时所存在的诸多不足，本文通过充分挖掘二次整数规划问题的结构特性来设计选择分枝变量与分枝方向的新方法，并将HNF算法与原问题松弛问题的求解相结合来寻求较好的初始整数可行解，由此导出可用于有效求解中大规模复杂二次整数规划问题的改进型分枝定界算法．数值试验结果表明所给算法大大改进了已有相关的分枝定界算法，并具有较好的稳定性与广泛的适用性．

A NEW BRANCH-AND-BOUND ALGORITHM FOR SOLVING LARGE COMPLEX INTEGER CONVEX QUADRATIC PROGRAMS

In view of disadvantages of usual branch-and-bound algorithms when they are used to solve high-dimensional complex integer quadratic programs, new methods for selecting the branching variable and node are devised by sufficiently utilizing Structural properties of integer quadratic programs. By combining the HNF algorithm and the solution of the original problem's continuous relaxation problem, a new technique for finding a good initial integer feasible solution is developed. These improvements result in a new branch-and-bound algorithm, which can be used to efficiently solve large-scale complex integer quadratic programs. Numerical results show that our new algorithm is not only a great enhancement on the existing branch-and-bound algorithms, but robust, efficient and suitable for different complex integer quadratic programming problems.