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

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

A Rigorous Method for Solving 0-1 Polynomial Knapsack Problem

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 maximum-flow 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.