The multiple knapsack problem denoted by MKP(B,S,m,n) can be defined as follows. A set B of n items j has a profit pj and weight wj, and knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP(B,S,m,n) is strongly NP-complete and no polynomial-time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years, semi-definite programming has been employed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm for MKP(B,S,m,n).
