Abstract:

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.

Key words: branch-and-bound method, Lagrangian relaxation, maximum-flow algorithm

0-1 polynomial knapsack problem