Matroidal relaxations for 0-1 knapsack problems

Lígia Amado, Paulo Bárcia

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

The family K of the feasible solutions for a 0-1 Knapsack with positive coefficients, K = {I ⊂ N:Σiε{lunate}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 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.

Original languageEnglish
Pages (from-to)147-152
Number of pages6
JournalOperations Research Letters
Volume14
Issue number3
DOIs
Publication statusPublished - 1 Jan 1993

Keywords

  • 0-1 knapsack
  • Lagrangean relaxation
  • matroids

Fingerprint Dive into the research topics of 'Matroidal relaxations for 0-1 knapsack problems'. Together they form a unique fingerprint.

  • Cite this