一类可分离的非线性0-1背包问题的分枝定界算法  

Branch and Bound Algorithm for Solving a Class of Nonlinear 0-1 Knapsack Problems

作　　者：段玉红[1] 高岳林[1] 

机构地区：[1]宁夏大学数学与计算机学院,宁夏银川750021

出　　处：《甘肃联合大学学报（自然科学版）》2006年第6期1-4,11,共5页Journal of Gansu Lianhe University :Natural Sciences

基　　金：国家民委科研项目(资助号:05XBE05)基金资助;宁夏高等学校科研项目基金资助(2005年)

摘　　要：构造出了一类可分离非线性0-1背包问题的分枝定界算法,分枝的过程是普通的0-1变量分枝,用简单的取整启发式法确定更好的可行解;而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近,由此得到最优值的一个下界.数值结果表明所提出的算法是有效的,可以求解中等规模的问题.A branch and bound algorlthm for solving a class of nonllnear 0-1 knapsack problems is proposed ,In whlch branching is common 0-1 varlables one and a better feaslble solutiong is found by a simply Integer hevrlstle method as well as a lower bound of the optlmal velue of the subproblem in the each branching node is determined by solving linear programming relaxed appronimate problem to be obtalned with linear relaned technique,It is shown by thd numerleal result that the algorlthm is effective and can solve the mlddle scale problems.

关 键 词：0-1背包问题 可分离凹规划 分枝定界方法 线性规划松弛 

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