多约束二次0-1背包问题的分支定界算法

摘要

In this paper,a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied.The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions.The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds Was determined with the outer approximation method.Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.