摘要
针对二次整数规划问题的特征,本文对传统分枝定界算法做了一系列的改进,其包括用HNF算法寻求初始整数可行解、对变量进行某种先验排序以确定分枝变量的选取次序、及针对变量的特性米选取分枝方向等,给出了可用于求解中大规模复杂二次整数规划问题的改进型分枝定界算法。数值试验结果表明所给算法大大改进了传统的分枝定界算法,并有广泛的适用性。
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.
出处
《工程数学学报》
CSCD
北大核心
2004年第3期371-376,416,共7页
Chinese Journal of Engineering Mathematics
基金
陕西省自然科学基金(2001SL09)资助项目.
关键词
二次整数规划
分枝定界法
HNF算法
integer quadratic programs
branch and bound: the HNF algorithm
