SEMI-DEFINITE RELAXATION ALGORITHM OF MULTIPLE KNAPSACK PROBLEM

• 作 者: ChenFeng YaoEnyu
• 机 构: Dept.ofMath.
• 出 处: 高校应用数学学报：英文版
• 发表日期: 2002年2期
• 关键词: 多背包问题 半定松弛算法 数值逼近 最优化 multiple knapsack problem semi- definite relaxation approx
• 基金项目: Supported by the National Natural Science Foundation of China(1 9971 0 78)

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a su