Search

The multiple knapsack problem denoted by MKP ( B,S,m,n) can be defined as follows. A set B of n items and a set S of m knapsacks are given such that each item j has a profit p j and weight w j , and each knapsack i has a capacity C i . 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 empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP ( B,S,m,n). It is proved that MKPS have a approximation ratio better than 0.5 for a subclass of MKP ( B,S,m,n) with n⩽100, m⩽5 and $$\frac{{max_{j = 1}^n \left\{ {w_j } \right\}}}{{min_{i = 1}^m \left\{ {C_i } \right\}}} \leqslant \frac{2}{3}$$ . [ABSTRACT FROM AUTHOR]