Facets for the Multiple Knapsack Problem

In this paper we consider the multiple knapsack problem which is defined as follows: given a set N of items with weights fi, i ∈ N, a set M of knapsacks with capacities Fk, k ∈ M, and a profit function cik, i ∈ N, k ∈ M; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper [?]