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

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

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems
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.

multi-dimensional quadratic 0-1 knapsack problem,branch-and-bound method,Lagrangian relaxation,outer approximation,surrogate constraint

孙娟、盛红波、孙小玲

展开 >

Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,P.R.China

multi-dimensional quadratic 0-1 knapsack problem,branch-and-bound method,Lagrangian relaxation,outer approximation,surrogate constraint

国家自然科学基金

10571116

2007

上海大学学报(英文版)
上海大学

上海大学学报(英文版)

影响因子：0.196
ISSN：1007-6417
年,卷(期)：2007.11(3)
  • 2
  • 11