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

针对二次整数规划问题的特征，本文对传统分枝定界算法做了一系列的改进，其包括用HNF算法寻求初始整数可行解、对变量进行某种先验排序以确定分枝变量的选取次序、及针对变量的特性来选取分枝方向等，给出了可用于求解中大规模复杂二次整数规划问题的改进型分枝定界算法。数值试验结果表明所给算法大大改进了传统的分枝定界算法，并有广泛的适用性。

A New Branch and Bound Algorithm for Solving Complex Integer Quadratic Programs

Based on integer quadratic programs' characteristics, carried out in this paper are a series of improvements on the traditional branch-and-bound algorithm, which include the determination of the initial integer feasible solution by the HNF algorithm, the branching variable selection according to an newly introduced priority of variables and the node selection by utilizing variables' specific properties. An practical new-type branch-and-bound algorithm suitable for medium and large-scak; complex integer quadratic programs is thus derived, numerical results illustrate that the new algorithm is not only a great improvement on the traditional branch-and-bound algorithm, but suitable for different, complex problems.