0-1多项式背包问题的一种精确算法  

A Rigorous Method for Solving 0-1 Polynomial Knapsack Problem

作　　者：盛红波[1] 孙娟[1] 孙小玲[1] 

机构地区：[1]上海大学理学院,上海200444

出　　处：《上海大学学报（自然科学版）》2006年第4期389-393,共5页Journal of Shanghai University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10571116)

摘　　要：提出了0-1多项式背包问题的一种新的精确算法.该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法.用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解.为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界;并且在分枝定界前,利用所得到的拉格朗日界,先固定最优解中某些变量的值.数值结果表明该算法是有效的.This paper proposes a rigorous algorithm for solving the 0-1 polynomial knapsack problem. The algorithm uses a branch-and-bound method based on Lagrangian relaxation and dual search. The upper bounds are computed with the outer approximation method where Lagrangian relaxations are solved with the maximumflow algorithm. Heuristic procedures are derived to search for feasible solutions, and some variables in the optimal solution are determined before the branch-and-bound process, thus improving performance of the algorithm. Promising computational results are reported for test problems.

关 键 词：0-1多项式背包问题 拉格朗日松弛 分枝定界法 最大流法 

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