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

A Rigorous Method for Solving 0-1 Polynomial Knapsack Problem

提出了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.