一类非负二次整数规划问题的分支定界缩减方法  

A BRANCH-AND-BOUND REDUCED METHOD FOR A CLASS OF NON-NEGATIVE INTEGER QUADRATIC PROGRAMMING PROBLEMS

作　　者：高岳林[1] 魏飞[1] 

机构地区：[1]北方民族大学信息与系统科学研究所,银川750021

出　　处：《计算数学》2011年第3期233-248,共16页Mathematica Numerica Sinica

基　　金：国家自然科学基金项目资助(60962006);宁夏自然科学基金项目资助(NZ0848)

摘　　要：针对一类非负整数二次规划问题,提出了一个新的分枝定界缩减方法.在这个方法里,使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减策略.数值结果表明所提出的算法是可行的和有效的.For a class of non-negative integer quadratic programming problems, a new branch- and-bound reduced method is proposed. In this method, a new rectangular two-partitioned technique and a new linear programming relaxation bounded technique are used. At the same time, in order to improve the degree of approximation and the convergence rate of acceleration, a rectangular reduction strategy is used. Numerical results show that the proposed algorithm is feasible and effective and can solve the middle-larger scale problems.

关 键 词：非负整数二次规划 分支定界 松弛技术 超矩形剖分 超矩形缩减 

分 类 号：O221.4[理学—运筹学与控制论]