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

摘要

提出了0-1多项式背包问题的一种新的精确算法.该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法.用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解.为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界;并且在分枝定界前,利用所得到的拉格朗日界,先固定最优解中某些变量的值.数值结果表明该算法是有效的.