Matroidal relaxations for 0-1 knapsack problems

The family K of the feasible solutions for a 0-1 Knapsack with positive coefficients, K = {I ⊂ N:Σ_iε{lunate}Ia_i≤b}, is an independence system over N = {1,...,n}. In some cases, for instance when all the a_i have the same value, this independence systems is a matroid over N. We will say then that the knapsack is greedy solvable. In the first part of this paper we study the conditions for a knapsack to be greedy solvable. We present necessary and sufficient conditions, verifiable in polynomial time, for K to be a member of a family of matroids over N. In the second part of the paper we study a family of matroidal relaxations for the 0-1 knapsack problem. We prove that those relaxations dominate the usual linear programming one for this problem and we present some computational results in order to illustrate that domination.