A carregar...
Publicação
Greedy Solvable Knapsacks: Identification and Relaxations
Autores
Orientador(es)
Resumo(s)
The family K of the feasible solutions for a 0-1 Knapsack with positive coefficients, K={l⊂N:Σi∈Iai≤b}, is an independence system over N={1,...,n}. In some cases, for instance when all the ai have the same value, this independence system 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 finite family of matroids over N. When those conditions are not met it seems natural to look for greedy solvable relaxations for the knapsack problem. 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.
Descrição
Palavras-chave
0-1 Knapsack Relaxations Matroids
Contexto Educativo
Citação
Amado, Lígia and Bárcia, Paulo, Greedy Solvable Knapsacks: Identification and Relaxations (April, 1992). FEUNL Working Paper Series No. 182